4. All possible subset 문제

임의의 정수 N에 대해 {0,1,2,...,N-1}의 가능한 모든 부분 집합을 출력하라

recursive 전략과 container 자료를 쓰면 편하게 되는 것 같다. recursive에서 분기를 2개로 나눠서 call하면 된다.

이런 문제의 경우 2^n의 시간 복잡도는 피할 수 없는 것 같다.

#include<iostream>
#include<vector>
using namespace std;
int S=0;
void PrintAllPosSet(int* arr, int size, int depth,vector<int> set) {
	if (depth == size) { //도달 : basis case
		cout << "{";
		for (vector<int>::iterator it = set.begin(); it != set.end(); it++)
			cout << *it << ", ";
		cout << "}" << endl;
		S++; //총 몇 개 집합 출력인지 세기 위해
	}
	else {
		vector<int> set_getDep = set;
		set_getDep.push_back(arr[depth]);
		PrintAllPosSet(arr, size, depth + 1, set);
		PrintAllPosSet(arr, size, depth + 1, set_getDep);
	}
	
}

int main() {
	vector<int> set;
	int arr[] = { 1,2,3,4,5,6,7,8,9,0 };
	int N = 10;
	PrintAllPosSet(arr, N, 0, set);
	cout << "총 " << S << "개의 집합을 출력하였음";
}

 

총 몇 개 집합을 출력했는지까지 테스트로 알 수 있게 짰다. STL은 배운지 얼마 안 돼서 열심히 연습 중이라 그 부분은 코드가 이상할 수 있다. 이것은 bitset으로 훨씬 빠르게 수행할 수 있는데 https://hezma.tistory.com/49?category=794955를 참고하면 될 것 같다.