문제 소개
숫자로 이루어진 집합이 하나 주어졌을 때, 그 집합으로 만들 수 있는 모든 부분집합을 생성해야 합니다. 이렇게 얻어진 전체 집합을 흔히 멱집합(power set)이라고 부릅니다. 다만 주의할 점은 집합의 요소들이 중복될 수 있다는 것입니다. 따라서 동일한 부분집합이 결과에 여러 번 등장하지 않도록 처리해야 합니다.
예를 들어 입력 집합이 [1,2,2]라면, 최종 멱집합은 다음과 같습니다.
[[], [1], [2], [1,2], [2,2], [1,2,2]]
풀이 접근 방법
이 문제는 재귀(recursion)를 활용한 백트래킹 기법으로 해결할 수 있습니다. 각 인덱스마다 “현재 요소를 부분집합에 포함한다 / 포함하지 않는다”는 두 가지 선택지를 모두 탐색하고, 완성된 부분집합을 집합(set) 자료구조에 기록해 중복을 걸러냅니다.
알고리즘 단계
- 결과 저장용 배열
res와 중복 검사용 집합x를 정의합니다. - 재귀 메서드
solve()는 현재 인덱스, 임시 배열(temp), 숫자 배열(nums) 세 가지를 인자로 받습니다. solve()함수는 아래와 같이 동작합니다.- 인덱스가 배열 v의 크기와 같다면:
- temp가 x에 존재하지 않으면 temp를 res에 삽입하고, 동시에 x에도 추가합니다.
- return으로 함수를 종료합니다.
solve(index + 1, temp, v)를 호출합니다. → 현재 요소를 포함하지 않는 경우v[index]를 temp에 삽입합니다.solve(index + 1, temp, v)를 다시 호출합니다. → 현재 요소를 포함하는 경우- temp의 마지막 요소를 제거해 이전 상태로 되돌립니다(백트래킹).
메인 함수의 처리 순서
- res와 x를 초기화하고, 입력 배열을 오름차순으로 정렬합니다.
- 빈 임시 배열 temp를 선언합니다.
solve(0, temp, array)를 호출해 탐색을 시작합니다.- 탐색이 끝나면 res를 정렬하여 반환합니다.
C++ 구현 코드
아래 예제를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
set < vector <int> > x;
static bool cmp(vector <int> a, vector <int> b){
return a < b;
}
void solve(int idx, vector <int> temp, vector <int> &v){
if(idx == v.size()){
if(x.find(temp) == x.end()){
res.push_back(temp);
x.insert(temp);
}
return;
}
solve(idx+1, temp, v);
temp.push_back(v[idx]);
solve(idx+1, temp, v);
temp.pop_back();
}
vector<vector<int> > subsetsWithDup(vector<int> &a) {
res.clear();
x.clear();
sort(a.begin(), a.end());
vector <int> temp;
solve(0, temp, a);
sort(res.begin(), res.end(), cmp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,2};
print_vector(ob.subsetsWithDup(v));
}
실행 결과 확인
입력
[1,2,2]
출력
[[],[1],[1, 2],[1, 2, 2],[2],[2, 2]]
핵심 정리
입력 배열을 미리 정렬해두면 동일한 값들이 인접하게 배치되어 결과가 일관된 순서로 출력되고, 집합 x를 이용한 중복 검사와 함께 사용하면 유니크한 부분집합만 깔끔하게 얻을 수 있습니다. 이 풀이의 시간 복잡도는 대략 O(2ⁿ × n)입니다. 각 요소마다 포함 여부를 선택하므로 부분집합이 최대 2ⁿ개 생성되고, 각 부분집합을 복사하고 집합에서 비교하는 데 최대 n의 비용이 추가로 들기 때문입니다.