描述
给定整数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题目思路：拿到这道题，看到从给定数列中选出若干个数，是它们的和恰好为K的时候，首先想到子集，用子集生成的递归算法，求出所有子集，判断符合条件的子集并且输出。后来想了半天，不知道怎么写。于是改变了思路。用深度搜索，从左往右，挨个元素搜索，但是递归的时候只搜索当前元素右边的元素。(其实就是求全排列的方法，只不过不搜左边，因为相同数字，顺序不同则是不同的排列，但却是相同的子集)。递归的边界是sum>=k，搜到以后直接停止搜索。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k;
int sum;
int a[22];
int vis[22];
int b;
void dfs(int cur){if(sum>=k){if(sum==k){b = 1;//用来判断是否存在有效输出 puts("YES");for(int i=0 ;i<n ;i++){if(vis[i])printf("%d ",a[i]);}puts("");}return ; }for(int i=cur ;i<n ;i++){sum += a[i];vis[i] = 1;//设计使用标记 dfs(i+1);//这里的变量是i+1 不是cur+1 因为不搜索左边 sum -= a[i];vis[i] = 0; //清除使用标记 }} int main(){while(scanf("%d%d",&n,&k)!=EOF){sum = 0;b=0;memset(vis,0,sizeof(vis));for(int i=0 ;i<n ;i++){scanf("%d",&a[i]);}dfs(0);if(!b)puts("NO");}return 0;
}
??