Recursive, Tree, Graph(DFS, BFS 기초) - 부분집합 구하기(DFS)

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

    public static void DFS(int L) {
        if (L == n + 1) {
            String tmp = "";
            for (int i = 1; i <= n; i++) {
                if (ch[i] == 1) tmp += i + " ";
            }
            if (ch.length > 0) System.out.println(tmp);
        } else {
            ch[L] = 1;
            DFS(L + 1);
            ch[L] = 0;
            DFS(L + 1);
        }
    }

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

- DFS(L+1)을 왼쪽 자식 오른쪽 자식 한번씩 실행된다고 생각한다. ch 배열로 1 과 0을 번갈아가며 주어 넣었다 뺐다한다.

공집합을 제외한 부분집합이 출력된다.

1 2 3 
1 2 
1 3 
1 
2 3 
2 
3