C++에서 사전순으로 멱집합(Power Set) 출력하기

문제 개요

이 문제에서는 문자열 str이 주어지며, 이 문자열의 원소들로 만들 수 있는 멱집합(Power Set)을 사전순(lexicographical order)으로 출력하는 것이 목표입니다.

멱집합이란?

멱집합(Power Set)은 어떤 집합 S의 모든 부분집합들을 원소로 가지는 집합을 의미하며, 일반적으로 P(S)로 표기합니다.

예시

S = {1, 2, 3}
P(S) = {{}, {1}, {1, 2}, {1, 3}, {2}, {2, 3}, {3}, {1, 2, 3}}

이 문제에서는 문자열을 하나의 집합으로 취급하기 때문에, 문자열을 구성하는 각 문자가 곧 집합의 원소가 됩니다.

문제 예시

입력 − str = "xyz"

출력 − x xy xyz xz y yz z

접근 방법

결과를 사전순으로 얻으려면 먼저 문자열을 오름차순으로 정렬해야 합니다. 정렬된 문자열을 기준으로 다음 과정을 통해 모든 부분집합을 생성할 수 있습니다.

문자열의 한 원소를 고정합니다.
고정된 원소 뒤에 올 수 있는 나머지 원소들에 대해 재귀적으로 함수를 호출하여 모든 부분 문자열(부분집합)을 생성합니다.
재귀 호출이 끝나면 마지막에 추가했던 문자를 제거하여 다음 조합을 탐색합니다.

n개의 원소를 가진 집합의 멱집합은 총 2ⁿ개의 부분집합을 포함하므로, 이 알고리즘의 시간 복잡도는 O(n × 2ⁿ)입니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

void printAllSubsets(string str, int n, int index = -1, string subset = "") {
    if (index == n)
        return;
    cout<<subset<<"\n";
    for (int i = index + 1; i < n; i++) {
        subset += str[i];
        printAllSubsets(str, n, i, subset);
        subset = subset.erase(subset.size() - 1);
    }
    return;
}

void GeneratePowerSet(string str) {
    sort(str.begin(), str.end());
    printAllSubsets(str, str.size());
}

int main() {
    string str = "xyz";
    cout<<"Power Set of the string '"<<str<<"' is :\n";
    GeneratePowerSet(str);
    return 0;
}

동작 원리

GeneratePowerSet 함수 − 문자열을 먼저 정렬한 뒤, printAllSubsets를 호출해 전체 탐색을 시작합니다. 정렬 단계 덕분에 생성되는 부분집합들이 자동으로 사전순을 유지하게 됩니다.
printAllSubsets 함수 − 현재까지 완성된 부분집합(subset)을 출력한 후, 현재 인덱스 이후의 문자들을 하나씩 추가하며 재귀 호출을 반복합니다. 재귀 호출이 반환되면 erase를 통해 마지막 문자를 제거하여 다음 경우의 수를 탐색합니다.

실행 결과

Power Set of the string 'xyz' is:
x
xy
xyz
xz
y
yz
z

이처럼 재귀와 백트래킹 기법을 활용하면 문자열의 모든 부분집합을 사전순으로 손쉽게 생성할 수 있습니다.