深度优先搜索(DFS,Depth-First Search)是搜索手段之一。它从某个状态开始，不断的转移状态知道无法转移，然后退回到前一步的状态，继续转移到其他状态，如此不断重复，直到找到最终的解。

问题给定整数a1,a2...an,判断是否可以从中选出若干数，使它们的和恰好为k。

 1<=n<=20

-1e8<=ai<=10e8

-1e8<=k<=1e8

输入：

 n=4 k=13

a={1 2 4 7}

输出：

Yes (13 = 2 + 4 + 7)

输入：

n=4 k=15

a={1 2 4 7}

输出：

No

枚举每一种情况复杂度为O(2^n)。利用dfs搜索可以枚举每一种情况代码如下：

#include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include 
          
           using namespace std;#define pi acos(-1)const int N=1e5;int n,a[N],ans[N],k;int h=0;bool dfs(int i,int sum)//ｉ代表第ｉ个数（从０开始）{ if(i==n) return sum==k; if(dfs(i+1,sum+a[i]))　//加入a[i]往下递归 { ans[h++]=a[i]; return true; } if(dfs(i+1,sum))//不加a[i]往下递归　　可以看成是加不加a[i]的问题（包括了所有状态） { return true; } return false;}int main(){ int i,j; while(scanf("%d%d",&n,&k)!=EOF) { h=0; for(i=0; i