部分和问题
时间限制：1000 ms | 内存限制：65535 KB
难度：2
- 描述
- 给定整数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 - 题解：这题用动态规划应该也能写，且时间效率高，用背包写了下，果断不对，思路有问题；
#include<stdio.h>
#include<stack>
using namespace std;
int m[],n,k;
stack<int>num;
bool dfs(int temp,int i){
if(i==n)return temp==k;
if(dfs(temp,i+))return true;
if(dfs(temp+m[i],i+)){
num.push(m[i]);
return true;
}
return false;
}
int main(){
while(~scanf("%d%d",&n,&k)){
for(int i=;i<n;++i)scanf("%d",&m[i]);
if(dfs(,)){
printf("YES\n");
for(int i=;!num.empty();i++){
if(i)printf(" ");
printf("%d",num.top());
num.pop();
}
puts("");
}
else printf("NO\n");
}
return ;
}
方法二：
#include<stdio.h>
const int MAXN=;
int m[MAXN],anser[MAXN];
int ans,k,n;
void dfs(int top,int num,int sum){
if(sum==k){
ans=;
puts("YES");
for(int i=;i<num;i++){
if(i)printf(" ");
printf("%d",anser[i]);
}
puts("");
return;
}
if(num>=n||top>=n)return;
for(int i=top;i<n;i++){
if(ans)return;
anser[num]=m[i];
dfs(i+,num+,sum+m[i]);
}
}
int main(){
while(~scanf("%d%d",&n,&k)){
ans=;
for(int i=;i<n;i++)scanf("%d",m+i);
dfs(,,);
if(!ans)puts("NO");
}
return ;
}