[Algorithm] Subset(부분집합) 구하기

재귀함수를 이용하여 부분집합을 구하는 방법이다. 

 

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

vector<int> subset;

void search(int k, int n) {
	vector<int>::iterator it;
	if (k == n + 1) {
		for (it = subset.begin(); it != subset.end(); it++) {
			cout << *it << " ";
		}
		cout << "\n";
	}
	else {
		subset.push_back(k);
		search(k + 1, n);
		subset.pop_back();
		search(k + 1, n);
		return;
	}
}

search 함수를 재귀적으로 호출하여 부분집합을 구한다. 

 

search 함수를 재귀 호출하는 분기가 일어나기 전에 push_back과 pop_back을 한번씩 호출하는데 

 

현재 단계인 k를 포함하여 재귀호출할 것인지, 포함하지 않고 재귀호출할 것인지에 따라 

 

부분집합의 결과가 달라진다. 

int main() {
	search(1, 4);
}

1~4까지의 부분집합을 구해본다. 

 

1 2 3 4
1 2 3
1 2 4
1 2
1 3 4
1 3
1 4
1
2 3 4
2 3
2 4
2
3 4
3
4