2-2-1. 부분집합 생성하기
부분집합을 생성하는 과정을 ‘원소 k’를 부분집합에 포함할 지, 아니면 포함하지 않을지로 결정하여 만들 수 있습니다.
- 이처럼 재귀를 진행하면서 k값을 포함 하는지, 안 하는지로 나누어 간다면 모든 부분집합을 구할 수 있습니다.
- 위의 상황은 n이 3일 때의 모든 부분집합을 구하는 과정입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> subset;
void search(int k){
if (k == n+1){
// 부분집합 모두 생성되었고, 처리
}
else {
// 1. k를 subset에 포함시킨다.
subset.push_back(k);
search(k+1);
// 2. k를 subset에 포함시키지 않는다.
subset.pop_back();
search(k+1);
}
}