部分和问题
|
试题描述
|
|
给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。 |
|
输入
|
|
第一行为两个整数n和k，n表示数的个数，k表示数的和。接下来一行为n个数a1、a2、...a。
|
|
输出
|
|
如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则输出“NO”
|
|
输入示例
|
|
4 13
1 2 4 7 |
|
输出示例
|
|
YES
2 4 7 |
|
其他说明
|
|
（1<=n<=20,保证不超int范围）
|
1 #include <iostream> 2 3 using namespace std; 4 int a[100001],b[100001]; 5 int n,k,cnt=0; 6 int dfs(int i,int sum) 7 { 8 if(i==n) return sum==k; //先判断当前的sum是否和k相等 9 //开始分类讨论 10 if(dfs(i+1,sum)==1) return 1; //不加上a[i+1] 11 if(dfs(i+1,sum+a[i])==1) {cnt++;b[cnt]=a[i];return 1;} //加上a[i+1] 12 return 0; //无论加不加上都不等于k 13 } 14 int main() 15 { 16 scanf("%d%d",&n,&k); 17 for(int i=0;i<n;i++) scanf("%d",&a[i]); 18 if(dfs(0,0)==1) //从最开始递归，一直在内部自己调用自己，最终返回一个值 19 { 20 printf("YES"); 21 printf(" "); 22 printf("%d",b[cnt]); //格式要求 23 for(int i=cnt-1;i>=1;i--) cout<<" "<<b[i]; 24 } 25 else printf("NO"); 26 //system("pause"); 27 return 0; 28 }
经典递归