[백트래킹/자바] 코드트리 IL. N개중에 M개 고르기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

이 문제는 주어진 범위에서 조합의 경우의 수를 구하는 문제이므로 전형적인 백트래킹 문제라고 할 수 있다. 여기서 필요한 것은, 중복이 허용되지 않는다는 것이다. 따라서 파라미터를 통해 시작점을 진행시키는 테크닉이 필요했다.

 

문제 풀이

public class n개중에_m개뽑기 {
    private static int n, m;
    private static Set<Integer> set = new TreeSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        go(1);


    }

    public static void go(int start) {
        if (set.size() == m) {
            set.forEach(e -> System.out.print(e + " "));
            System.out.println();
            return;
        }
        for (int i = start; i <= n; i++) {
            set.add(i);
            int next = i + 1;
            go(next);
            set.remove(i);
        }
    }
}