部分和问题
描述 给定整数a1、a2、…….an，判断是否可以从中选出若干数，使它们的和恰好为K。
输入 首先，n和k，n表示数的个数，，k表示数的和。 接着一行n个数。 （1<=n<=20,保证不超int范围） 输出 如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO” 样例输入
4 131 2 4 7
样例输出
YES2 4 7
题目分析： 这是一道经典的dfs问题，好多公司也用它做过面试题，我们定义函数dfs(k,i)：对于组成k的几个数，有两种方法， 一、使用第i个值，下一步搜索dfs（k-a[i]，i+1）; 二、不适用第i个值，搜索dfs（k，i+1） if（k==0）证明找到了解，return； return的还有另外一种可能，就是搜索到第N+1个还使k=0，也要返回。
AC代码：
/** *@xiaoran *dfs */;int n,k,a[22],b[22],ok;void dfs(int k,int i){//已经找到解或者已经到达数组尾部返回，注意此时到n+1if(ok||i==n+1) return ;//找到了解if(k==0){cout<<“YES”<<endl;for(int i=0;i<n;i++){if(b[i]==1){cout<<a[i]<<” “;}}cout<<endl;ok=1;return;}//if(k<0) return ;if(b[i]==0&&k-a[i]>=0){//没有使用b[i]=1;//记录使用的值，便于输出dfs(k-a[i],i+1);//使用第i个值，进行搜索b[i]=0;}dfs(k,i+1);//不使用第i个值进行搜索}int main(){/*#ifdef LOCALfreopen(“input.txt”,”r”,stdin);freopen(“output.txt”,”w”,stdout);#endif*/while(cin>>n>>k){memset(b,0,sizeof(b));ok=0;for(int i=0;i<n;i++){cin>>a[i];}dfs(k,0);if(ok==0) cout<<“NO”<<endl;}return 0;}
每个人心中，都会有一个古镇情怀，流水江南，烟笼人家。
