Advanced05 백트래킹 (2)부분집합

1) 소개

* 파워셋(power set) : 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합.

- 구하고자 하는 집합의 원소 개수 : n => 부분집합 개수 : 2^n

- 백트래킹 기법으로 power set 구하기

- n개의 원소를 포함하는 집합에는 2^n개의 부분 집합이 있음.

- n개의 비트열을 사용하여 부분 집합 표현 가능. (1 또는 0 값을 가지는 n개의 배열을 만드는 방법 이용.)

** 비트열 배열의 i번 인덱스 값 = 집합의 i번 인덱스 원소의 부분 집합 포함 여부 표현.(1:포함, 0:미포함)

ex) 크기가 4인 배열의 부분집합 구하기.

- 자식 노드가 항상 2개인 이진트리.

오른쪽 자식(1) 방문 : 포함, 왼쪽 자식(0) 방문 : 미포함.

높이가 1인 노드 : 첫 번째 원소의 포함 여부를 선택한 상태.

높이가 2인 노드 : 두 번째 원소의 포함 여부를 선택한 상태.

... 총 4번을 선택하면 하나의 부분집합을 표현하게 됨.

루트 ~ 단말 노드 경로에 포함된 4개의 간선에 부여된 값을 모으면 => 하나의 부분집합을 표현하는 비트열이 됨.

* 실제 subset함수의 호출 트리

상태공간트리와 동일함..!

높이 k에 위치한 노드 = k번 선택이 이루어진 상태를 의미함.

/* (2) 부분집합
총 원소가 4개인 {A,B,C,D} 집합이 있다.
만들 수 있는 모든 부분집합을 출력하라.
*/
#include<iostream>
 
using namespace std;
 
char arr[4] = {'A', 'B', 'C', 'D'};
int bit[4];
 
void subset(int k, int n) {
    if (k == n) {
        cout << "{";
        for (int i = 0; i < n; i++) {
            if (bit[i] == 1) {
                // 부분집합 원소들 사이에 ", " 포함해서 출력하려고..
                // A가 첫번째 출력될땐 ", " 출력 안되도록 함. 
                // but, B, C, D가 첫번째 출력될 땐 ", "이 출력된다ㅠㅠ
                if(i != 0)
                    cout << ", ";
                cout << arr[i];
            }
        }
        cout << "}" << endl;
    }
    
    else {
        bit[k] = 0;
        subset(k + 1, n);
        bit[k] = 1;
        subset(k + 1, n);
    }
}
 
int main() {
    subset(0, 4);
 
    return 0;
}

// 실행 결과

{}

{, D}

{, C}

{, C, D}

{, B}

{, B, D}

{, B, C}

{, B, C, D}

{A}

{A, D}

{A, C}

{A, C, D}

{A, B}

{A, B, D}

{A, B, C}

{A, B, C, D}

계속하려면 아무 키나 누르십시오 . . .

 부분집합을 "," 포함해서 이쁘게 출력하는게 잘 안된다.