재귀 함수를 이용한 부분 집합 생성 알고리즘

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

vector<int> subset;
int n = 4;

void search(int k) {
	if (k == n + 1) {
		// 부분 집합 출력
		for (int i = 0; i < subset.size(); i++)
			cout << subset[i] << " ";
		cout << endl;
	}
	else {
		subset.push_back(k); // k를 부분집합에 포함시킨다.
		search(k + 1);
		subset.pop_back(); // k를 부분집합에 포함시키지 않는다.
		search(k + 1);
	}
}

int main() {
	search(1);
}

 

1부터 n까지의 숫자로 만들 수 있는 부분 집합의 경우의 수를 출력하는 함수다.

마지막 공집합은 빈 줄로 출력이 되기 때문에 실수로 놓치는 것에 주의한다.

 

우리가 부분집합을 손으로 (가지치기하여) 구할 때와 유사한 방식이라고 생각한다.

다만 재귀알고리즘은 익숙하지않으면 코드 자체를 보고 실행결과를 예상하기가 힘들다.

---

실행 결과: