部分和问题（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

 1  //不保存符合条件的每一个数
 2   #include<iostream>
 3   int a[25];
 4   int n,k;//全局变量
 5   using namespace std;
 6   bool dfs(int i,int sum){//已经从前i项得到了和sum，然后从i项之后进行深度搜索 
 7      if(i==n+1)
 8           return sum==k; //如果前n项都计算过了，则返回并判断sum是否与K相等 
 9       if(dfs(i+1,sum))//不加a[i]的情况 
10          return true;
11      if(dfs(i+1,sum+a[i]))//加上a[i]的情况 
12          return true;
13      return false;  //无论加上a[i]还是不加上a[i]都不能使得sum==k，则返回flase 
14  }
15  int main(){
16      cin>>n>>k;
17      for(int i=1;i<=n;i++)
18          cin>>a[i];
19      if(dfs(1,0))//从1开始，因为题目中1<=n<=20 
20          cout<<"YES"<<endl;
21      else
22          cout<<"NO"<<endl;
23      return 0;
24  }
25 //深度优先搜索从最开始的状态出发，遍历所有可以达到的状态，由此可以对所有的状态进行操作，或列举出所有的状态

保存并输出符合条件的数据：

 1 #include<iostream>
 2 int a[25],b[25]={0};//b[25]初始化零，用于标记符合条件的数据 
 3 int n,k;
 4 using namespace std;
 5 int dfs(int i,int sum)
 6 {
 7     if(i==n+1&&sum==k)
 8         return 1;
 9     if(i==n+1&&sum!=k)
10         return 0;
11     b[i]=0;//标记为0，数据不符合 
12     if(dfs(i+1,sum))
13         return 1;
14     b[i]=1;//标记为1，数据符合 
15     if(dfs(i+1,sum+a[i]))
16         return 1;
17     return 0;
18 }
19 int main()
20 {
21     while(cin>>n>>k){
22         int p=0;
23     for(int i=1; i<=n; i++)
24         cin>>a[i];
25     if(dfs(0,0)){
26         cout<<"YES"<<endl;
27         for(int i=1; i<=n; i++){
28             if(b[i])
29                 cout<<a[i]<<" ";
30         }
31         cout<<endl;
32     }
33     else
34         cout<<"NO"<<endl;
35     }
36     
37     return 0;
38 }

测试结果：