N과 M (4)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A₁ ≤ A₂ ≤ ... ≤ A_K-1 ≤ A_K를 만족하면, 비내림차순이라고 한다.

https://www.acmicpc.net/problem/15652

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();

        int N = Integer.parseInt(input.split(" ")[0]);
        int M = Integer.parseInt(input.split(" ")[1]);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        solution(N, M, bw);
        bw.flush();
    }

    public static void solution(int N, int M, BufferedWriter bw) throws IOException {
        int[] array = new int[N];

        for (int i = 0; i < N; i++) {
            array[i] = i + 1;
        }

        int[] current = new int[M];
        dfs(array, current, 0, 0, M, bw);
    }

    public static void dfs(int[] array, int[] current, int start, int depth, int count, BufferedWriter bw) throws IOException {

        if (depth == count) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < current.length; i++) {
                sb.append(current[i]).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;
        }

        for (int i = start; i < array.length; i++) {
            current[depth] = array[i];
            dfs(array, current, current[depth]-1, depth + 1, count, bw);
        }
    }

}