NYOJ 1058 部分和問題 [DFS]

部分和問題

描述

給定整數a1、a2、.......an，判斷是否可以從中選出若干數，使它們的和恰好為K。

輸入

首先，n和k，n表示數的個數，k表示數的和。
接著一行n個數。
（1<=n<=20,保證不超int范圍）

輸出

如果和恰好可以為k，輸出“YES”，並按輸入順序依次輸出是由哪幾個數的和組成，否則“NO”

樣例輸入

4 13
1 2 4 7

樣例輸出

YES
2 4 7

簡單的深搜

 

 

#include 
int n, k, ok, arr[22], vis[22], count;

void DFS(int pos){
	if(count >= k){
		if(count == k){
			if(!ok){
				ok = 1; printf("YES\n");
			}
			for(int i = 0; i < n; ++i)
				if(vis[i]) printf("%d ", arr[i]);
			printf("\n");
		}
		return;
	}
	
	for(int i = pos; i < n; ++i){
		count += arr[i];
		vis[i] = 1;
		DFS(i + 1);
		count -= arr[i];
		vis[i] = 0;
	}
}

int main(){
	while(scanf("%d%d", &n, &k) == 2){
		ok = 0;
		for(int i = 0; i < n; ++i){
			scanf("%d", arr + i);
			vis[i] = 0;
		}
		count = 0; DFS(0);
		if(!ok) printf("NO\n");
	}
	return 0;
}