DFS - 부분집합구하기

숫자를 입력받고 그 수의 부분집합을 한칸씩 띄어주며 모두 구하라.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,ch[11];
void D(int L)
{
	int i;
	if (L == n + 1) {
		for (i = 1; i <= n; i++)
		{
			if (ch[i] == 1)cout << i;
		}
		cout << endl;
	}
	else {
		ch[L] = 1;
		D(L + 1);
		ch[L] = 0;
		D(L + 1);
	}
}
int main() {
	cin >> n;
	D(1);
	return 0;
}

 

DFS는 트리형식으로 만들어 이해해야한다. 학부생때 보고 배우기만 했지 처음 구현해보는 알고리즘 구조라 이해하는데 정말 오래걸렸다. 지금도 이해는 가지만 응용하기에는 더 많은 공부가 필요할것같다. 따라서 난 이 알고리즘이 어떻게 함수를 호출하고 복귀하는지 보기쉽게 트리로만들어 그려보았다.

본 알고리즘 동작 과정