7. 부분집합(DFS 완전탐색)

 

    7번 문제   

 

---

 

 

    내가 풀이한 답   

 

 

 위의 그림과 같이 완전탐색으로 n 값에 대한 부분집합을 구할 수 있다. 해당 숫자를 포함하는 경우와 포함하지 않는 경우를 나누면 해결할 수 있다.  

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, check[11];
 
void dfs(int level){
	if(level==n+1){
		for(int i=1; i<=n; i++){
			if(check[i]==1) cout << i << " ";
		}
		cout << endl;
	}
	else {
		check[level] = 1;
		dfs(level+1);
		check[level] = 0;
		dfs(level+1);
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	cin >> n;
	
	dfs(1);
	return 0;
}

 

---

 

    사이트의 답안   

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, ch[100];
void DFS(int L){
	int i;
	if(L==n+1){
		for(i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ", i);
		}
		puts("");
	}
	else{
		ch[L]=1;
		DFS(L+1);
		ch[L]=0;
		DFS(L+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	return 0;
}