[알고리즘] 완전 탐색 - 조합 (백준 15650번. N과 M(2) - JAVA)

조합

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

(1) 중복 없이 (2) 고르기

 

ex) 조합은 순서가 없으므로 [1,2] 와 [2,1]을 같은 것으로 취급한다. 

 

백준 15650번. N과 M(2)

 

조건 

 

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

풀이 방법

• 재귀 사용(백트래킹)
• Scanner + StringBuffer 
• 현재 선택한 원소 이후의 것들을 선택 가능하므로 start 변수를 +1씩 해서 넘겨준다. 

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] out;
    static boolean[] visited;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();

        out = new int[M];
        visited = new boolean[N+1];

        combination(0, 1, out);
        System.out.println(sb);


    }

    private static void combination(int depth, int start, int[] out) {
        if(depth == M){
            for(int num : out) sb.append(num).append(" ");
            sb.append("\n");
            return;
        }

        for(int i = start; i<=N; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = i;
                combination(depth+1, start+=1, out);
                visited[i] = false;
            }
        }
    }
}