[백준] 15650번 N과 M (2)

N과 M (1)은 순열이었다면 N과 M (2)는 조합이다.

단계별로 풀어보기 백트래킹의 2단계 문제이다.

15650번: N과 M (2)

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        boolean[] visited = new boolean[n];
        int[] result = new int[m];
        combination(n, m, 0, visited, result);
    }

    static void combination(int n, int m, int num, boolean[] visited, int[] result) {
        if (num == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
        }
        else {
            for (int i = 0; i < n; i++) {
                if(!visited[i]) {
                    if(num != 0) {
                        if (result[num - 1] < i + 1) {
                            visited[i] = true;
                            result[num] = i + 1;
                        }
                        else continue;
                    }
                    else {
                        visited[i] = true;
                        result[num] = i + 1;
                    }
                    combination(n, m, num + 1, visited, result);
                     visited[i] = false;
                }
            }
        }
    }
}

응용할 것도 없이 그냥 조합이기 때문에 쉽게 풀 수 있었다.