[백준] 15649번: N과 M (1)

백트래킹을 사용해서 구현했다.
백트래킹: 재귀적으로 문제를 해결하되 제한 조건에 위배되는지 판단하여 위배되는 경우를 제외하고 다음 단계로 넘어간다.

1~n까지 자연수 중에서 중복 없이 r개를 고른 수열을 구한다.
1~n까지 탐색하기 위한 check와 결과값을 저장하기 위한 results를 사용해서 백트래킹을 구현했다.
백트래킹 제한 조건: r개를 고른다.
n번 재귀한다.

처음엔 int 배열을 만들기 싫어서 StringBuilder에 append()를 사용하여 출력값을 저장했다. 그런데 어째서인지 제대로 출력이 되지 않아서 int 배열을 사용했다.

package exercises.backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Math15649 {
    static boolean[] check;
    static int[] results;
    static int n;
    static int r;
    static StringBuilder sb = new StringBuilder();
    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());
        r = Integer.parseInt(st.nextToken());
        check = new boolean[n];
        results = new int[r];
        backTracking(0);
        System.out.print(sb);
    }

    static void backTracking(int cnt) {
        if(cnt == r) {//숫자의 갯수
            for(int num: results) sb.append(num).append(" ");
            sb.append("\n");
            return;
        }
        for(int i=0; i<n; i++) {//반복 횟수
            if(!check[i]) {
                check[i] = true;
                results[cnt] = i+1;
                backTracking(cnt+1);//다음
                check[i] = false;
            }
        }
    }
}