N과 M (5)

문제

15654번: N과 M (5)

문제 설명

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

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

제한 사항

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

입출력 예

입력	출력
3 1	2
4 5 2	4
	5
4 2	1 7
9 8 7 1	1 8
	1 9
	7 1
	7 8
	7 9
	8 1
	8 7
	8 9
	9 1
	9 7
	9 8
4 4	1231 1232 1233 1234
1231 1232 1233 1234	1231 1232 1234 1233
	1231 1233 1232 1234
	1231 1233 1234 1232
	1231 1234 1232 1233
	1231 1234 1233 1232
	1232 1231 1233 1234
	1232 1231 1234 1233
	1232 1233 1231 1234
	1232 1233 1234 1231
	1232 1234 1231 1233
	1232 1234 1233 1231
	1233 1231 1232 1234
	1233 1231 1234 1232
	1233 1232 1231 1234
	1233 1232 1234 1231
	1233 1234 1231 1232
	1233 1234 1232 1231
	1234 1231 1232 1233
	1234 1231 1233 1232
	1234 1232 1231 1233
	1234 1232 1233 1231
	1234 1233 1231 1232
	1234 1233 1232 1231

입출력 예 설명

아이디어

dfs 순열 만드는 백트래킹

제출 코드

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

public class three15654 {
    private static int n;
    private static int m;
    private static int[] numbers;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();
    private static int[] sequence;

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        numbers = new int[n];
        sequence = new int[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }

        Arrays.sort(numbers);
        permutation(0);

        System.out.println(sb.toString());
    }

    private void permutation(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                sb.append(sequence[i]).append(" ");
            }
            sb.append('\n');
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sequence[depth] = numbers[i];
                permutation(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        new three15654().solution();
    }
}