本文共 784 字，大约阅读时间需要 2 分钟。

给n个数 a1,a2,....ak  ，判断是否有其中的一些数的和 等于 k；

例如

n = 2

k = 3

集合{1,2}

DFS：

#include
   
    using namespace std;#define MAX 1005int a[MAX];int n, k;int flag;int cnt;bool dfs(int cur, int s)	{		if(cur == n+1){			cout <<"cnt = " <
    
     <<" ";				if(s==k)				cout <<"true";			else cout <<"false"	;			return s == k;		}		if(dfs(cur+1,s)) return true;//false时候不做处理  true时候就返回 true 		if(dfs(cur+1,s+a[cur])) return true;//所以有一个符合条件就可以 		return false;	}int main()	{		int x;		cin >> n >> k;		for(int i = 1; i <= n; ++i){			scanf("%d",&x);			a[i] = x;		}		flag = 0;		if(dfs(1,0)){			cout <<"Yes\n";		}		else{			cout << "No\n";		}				return 0;		}
    
   

图中 是 递归过程 最开始s = 0，  然后第一步时候由于需要判断第一个数是否要被加上产生的分叉, 左侧 加上第一个数 结果变为 1， 右侧没加1结果仍旧为0，

接着继续往下分叉 ， 这里 每次每次分叉 只要结果为true就返回 true，除非所有分叉的结果 都是false才返回false。