N과 M (5)

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

• N개의 자연수 중에서 M개를 고른 수열

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

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

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]);

        input = sc.nextLine();

        String[] nums_s = input.split(" ");
        int[] nums = new int[nums_s.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.parseInt(nums_s[i]);
        }

        Arrays.sort(nums);

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

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

        dfs(nums, current, isUsed, 0, M, bw);

    }

    public static void dfs(int[] nums, int[] current, boolean[] isUsed, 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 = 0; i < nums.length; i++) {

            if (isUsed[i]) {
                continue;
            }
            isUsed[i] = true;
            current[depth] = nums[i];
            dfs(nums, current, isUsed, depth + 1, count, bw);
            isUsed[i] = false;
        }
    }
}