알고리즘) 배열의 모든 부분집합 구하기(DFS)

문제

 1부터 주어지는 수 N까지의 수를 중복되지 않게 가지는 배열이 존재한다고 할 때, 공집합을 제외하고 가능한 모든 부분집합을 출력

public class Main {
    static int n;
    static int[] result;

    static void dfs(int k) {
        if (k == n + 1) {
						String str = "";
            for (int i = 1; i <= n; i++) {
                if (result[i] == 1) str += i + " ";
            }
            if (str.length() > 0) System.out.println(str);
        } else {
            int L = 1;
            result[k] = L;
            dfs(k + 1);

            L = 0;
            result[k] = L;
            dfs(k + 1);
        }
    }

    public static void main(String[] args) {
        n = 3;
        result = new int[n + 1];
        dfs(1);
    }
}

 

유의할 점

배열의 길이 N의 값에 임의로 3을 부여

 재귀 메서드를 사용하며, 해당 노드(원소)를 부분배열에 넣겠다는 의미로는 1을, 넣지 않겠다는 의미로는 0을 사용하여 이진트리를 구성한다. 노드 수 + 1 만큼의 길이를 가지는 배열을 만들어 모든 경우의 수를 구한다. (해당 배열[노드값] = ‘0 또는 1’의 형태로 사용)

 재귀 메서드에들어오는 노드값이 N보다 커지는 순간 재귀를 종료하고 결과를 출력한다. (모든 부분 배열을 구하는 경우의 수는 노드값이 N보다 커지면서 마무리된다.)