09H:数字组合(示例代码)

fangziyuan 2020-12-10

栏目: 类库 ·

来源: fangziyuan

作者:fangziyuan

简介  这篇文章主要介绍了09H:数字组合(示例代码)以及相关的经验技巧,文章约3442字,浏览量200,点赞数6,值得推荐!

总时间限制: 
1000ms
 
内存限制: 
65536kB
描述
有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如:
n=5,5个数分别为1,2,3,4,5,t=5;
那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
输入
输入的第一行是两个正整数n和t,用空格隔开,其中1<=n<=20,表示正整数的个数,t为要求的和(1<=t<=1000)
接下来的一行是n个正整数,用空格隔开。
输出
和为t的不同的组合方式的数目。
样例输入
5 5
1 2 3 4 5
样例输出
3
 1 #include<iostream>
 2 #include<cstring> 
 3 using namespace std;
 4 int a[25];
 5 int n, t;
 6 int divide(int step, int left){
 7     if(step==n&&left!=0) return 0;
 8     if(left == 0) return 1;
 9     return divide(step+1, left-a[step])+divide(step+1, left);
10 }
11 int main(){
12     cin>>n>>t;
13     int i;
14     for(i = 0 ; i < n; i++)
15         cin>>a[i];
16     int ans = divide(0, t);
17     cout<<ans<<endl;
18     return 0;
19 }

备注:看一眼数据范围,全部枚举的话2^20也就是一百多万,完全可以,所以就直接递归就行了。

总方案数目= 包含第一个数的方案数+不包含第一个数的方案数,每次这么划分就行。

 


以上就是本文的全部内容,希望对大家的学习有所帮助,本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 原文地址:https://www.cnblogs.com/fangziyuan/p/13098498.html

相关文章

数字组合(示例代码)

2985:数字组合(示例代码)

2985:数字组合(示例代码)

1056. 组合数的和(15)

实例001:数字组合

B1056 组合数的和 (15分)

#DP# ----- 数字组合(示例代码)

PAT——1056. 组合数的和