[알고리즘] 부분집합(Subset)

부분집합(Subset)

개념

- 집합에 포함된 원소들을 선택하는 것

- 아무 것도 안 뽑는 것부터 전체 다 뽑는 것까지 조합의 경우를 다 더한 것과 같음

- 부분집합을 이용하여 조합으로 사용하고 싶으면 지금까지 선택한 원소의 개수가 r개가 되면 조합을 구할 수 있음

- 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개

- 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합

 

구현

- 하나의 원소에 대해서 선택, 비선택 하는 과정을 재귀로 진행

- isSelected[cnt] = true : 선택

- Subset(cnt+1) : 다음 원소 (선택에 대한 처리하면서 뒤에 따라오는 모든 경우를 따짐)

- isSelected[cnt] = false : 비선택

- Subset(cnt+1) : 다음 원소

- cnt : 고려해야하는 현재 원소가 몇 번째 원소인지

- 기저조건 : cnt == N(마지막 원소까지 부분집합에 다 고려)

 

코드

public static void subset(int cnt){
        if(cnt == N){
            // 마지막 원소까지 부분집합에 다 고려되었을 때
            // 출력해보기
            for(int i = 0; i<N; i++){
                System.out.print((isSelected[i] ? input[i] : "X") + " ");
            }
            System.out.println();
            return;
        }

        // 선택
        isSelected[cnt] = true;
        subset(cnt+1);
        // 비선택
        isSelected[cnt] = false;
        subset(cnt+1);
}