재귀 - 부분집합, 순열

<부분집합>

n개의 요소를 가진 배열에 대한 부분집합을 만든다면 총 2^n개의 부분집합이 나올 것.

 

각각의 요소들마다 부분집합에 포함하거나 포함하지 않거나 둘 중 하나이므로 2^n개의 부분집합이 생기는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 5;

vector<int> subset;
int a[MAX],n;

void make_subset(int k) { //k는 위치
	if (k == n) {
		if (subset.empty())
			cout << "공집합\n";
		for (int i : subset)
			cout << i << " ";
		cout << '\n';
		return;
	}
	subset.push_back(a[k]);
	make_subset(k + 1);
	subset.pop_back();
	make_subset(k + 1);
}

int main() {
	cout << "n 입력: ";
	cin >> n;
	cout << "n개의 배열을 입력: ";
	for (int i = 0; i < n; i++)
		cin >> a[i];

	make_subset(0);
}

 

---

<순열>

https://suuntree.tistory.com/16

BOJ 15649 - N과 M (1~12)

이걸로 대체