C++로 집합의 모든 고유한 부분집합(멱집합) 구하는 방법

이번 글에서는 주어진 집합의 모든 고유한 부분집합을 출력하는 방법을 알아보겠습니다. 예를 들어 집합이 {1, 2, 3}이라면 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}이 됩니다.

이렇게 한 집합의 모든 부분집합의 집합을 멱집합(Power Set)이라고 하며, 원소가 n개인 집합의 멱집합은 정확히 2ⁿ개의 부분집합을 가집니다.

접근 방법: 비트마스킹

가장 간단한 방법은 비트 연산을 활용하는 것입니다. 0부터 2ⁿ-1까지의 숫자를 하나씩 순회하면서, 현재 카운터 값의 i번째 비트가 1로 설정되어 있으면 집합의 i번째 원소를 해당 부분집합에 포함시키는 방식입니다.

예를 들어 n=3일 때 카운터 값이 5(이진수로 101)라면, 0번째와 2번째 비트가 설정되어 있으므로 부분집합은 {a, c}가 됩니다. 이처럼 각 숫자를 부분집합에 대한 고유한 표현으로 사용할 수 있습니다.

예제 코드

#include<iostream>
#include<cmath>
using namespace std;

void showPowerSet(char *set, int set_length) {
    unsigned int size = pow(2, set_length);
    for(int counter = 0; counter < size; counter++) {
        cout << "{";
        for(int j = 0; j < set_length; j++) {
            if(counter & (1<<j))
                cout << set[j] << " ";
        }
        cout << "}" << endl;
    }
}

int main() {
    char set[] = {'a','b','c'};
    showPowerSet(set, 3);
}

실행 결과

{}
{a }
{b }
{a b }
{c }
{a c }
{b c }
{a b c }

동작 원리 살펴보기

코드의 핵심은 내부 반복문의 조건식 counter & (1<<j)입니다. 이 식은 비트 AND 연산을 통해 카운터 값의 j번째 비트가 켜져 있는지 확인합니다.

• counter = 0 (000): 어떤 비트도 설정되지 않음 → 빈 집합 {}
• counter = 1 (001): 0번째 비트만 설정 → {a}
• counter = 3 (011): 0번째, 1번째 비트 설정 → {a, b}
• counter = 7 (111): 모든 비트 설정 → {a, b, c}

시간 복잡도

멱집합의 크기가 2ⁿ이고, 각 부분집합을 만드는 데 최대 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n × 2ⁿ)입니다. 멱집합 자체가 지수적으로 커지기 때문에 n이 작은 경우(대략 20~25 이하)에 실용적입니다.