DFS 부분집합 찾기

 

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,ch[20];

//후위순회 출력 
void D(int L){
	if(L==n+1){
		for(int i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ",i);
		}
		printf("\n");
	}
	else{
		ch[L]=1;
		D(L+1);
		
		ch[L]=0;
		D(L+1);	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	D(1);

	return 0;	
}

부분집합 찾기

 

 

 

 

 

 

 

-----

활용

합이 같은 부분집합 찾기

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,arr[11],ch[20],sum;
bool already_yes = false;
void DFS(int x){
	if(already_yes) return;
	if(x==n + 1){
		int half = 0;
		for(int i=1; i<=n; i++){
			if(ch[i]==1){
				half+=arr[i];
				
				//printf("%d ",arr[i]);
			}
		}
		//printf("\n");
		if(sum==2*half){
			printf("YES");
			already_yes = true;
			return;
		}
	}	
	else{
		ch[x] = 1;
		DFS(x+1);
		
		ch[x] = 0;
		DFS(x+1);
	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d", &arr[i]);
		sum+=arr[i];
	}
	
	DFS(1);
	if(!already_yes) printf("NO");

	return 0;	
}

 

매개변수를 이용해 간결하게 표현할 수 있다

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,a[11],total=0;
bool end;
void DFS(int L,int sum){
	if(end) return;
	if(L==n+1){
		if(sum*2 == total){
			printf("YES");
			end = true;
		}
	}
	else{
		DFS(L+1, sum+a[L]);	
		DFS(L+1, sum);
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1,0);


	if(!end) printf("NO");
	return 0;	
}