09H:数字组合

总时间限制:: 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

样例输出

 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也就是一百多万，完全可以，所以就直接递归就行了。

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