모든 경우의 수 (백 트래킹)

우연히 백트래킹 공부하다가 이전에 비트연산으로 만들었던 경우의 수를 백트래킹으로 구현해보았다.

백트래킹은 다른 DFS와는 다르게 함수안에 반복문이 구현되어있다.

문제 이해 하고 설명 하도록 하겠습니다. ㅈㅅ;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    static int[] arr;
    static int[] result;
    static int N;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        while (true) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]);
            if (N == 0) {
                break;
            }
            arr = new int[N];
            result = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(str[i + 1]);
            }
            DFS(0, 0);
        }
 
    }
 
    public static void DFS(int start, int depth) {
    
        for (int i = start; i < N; i++) {
            result[i] = 1;
            DFS(i + 1, depth + 1);
            result[i] = 0;
        }
        print();
    
        
        
    }
 
    public static void print() {
        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
}
 

반대로 출력하고 싶다면 

result[i] = 0;

DFS(i + 1, depth + 1);

result[i] = 1;

으로 바꾸면 된다.