백준에 있는 문제 중 1182번을 풀면서 부분집합에 대한 내용이 나와서 간단하게 정리하려고 한다.

예를 들어 배열 [1,2,3]이 있다고 가정하자. 그러면 부분집합은 아래와 같다.

[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

부분 집합을 구할 수 있는 방법은 조합을 이용한 방법이 있고 재귀를 이용한 방법이 있다. 이번에는 후자인 재귀에 대해서만 알아보도록 하겠다.

두 가지 경우를 생각해보면 된다.

  1. 현재 인덱스를 포함하는 경우
  2. 현재 인덱스를 포함하지 않는 경우

위의 두 가지 경우를 visited 배열에 방문했는지 체크함으로써 분기시킬 수 있다. 두 가지 경우에 대해서 모두 확인한 후에 현재 인덱스가 n이 되면 출력한다.

출력할 때는 visited 배열의 값이 true인 원소들만 출력한다.
코드는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Main {
    private static int n = 3;
    private static boolean[] visited = new boolean[n];

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        getSet(arr, 0);
    }

    private static void getSet(int[] arr, int index) {
        if (index == n) {
            print(arr);
            return;
        }

        visited[index] = false;
        getSet(arr, index + 1);

        visited[index] = true;
        getSet(arr, index + 1);

    }

    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if(visited[i]){
                System.out.print(arr[i]+" ");
            }
        }
        System.out.println();
    }
}
// 결과
3 
2 
2 3 
1 
1 3 
1 2 
1 2 3

참고