A38314. 数字组合有 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<=1 000) 接下来的一行是 n 个正整数， …
填空题
较难
知识点
题目描述
数字组合
有 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<=1 000) 接下来的一行是 n 个正整数， 用空格隔开。
输出
和为 t 的不同的组合方式的数目 。
样例输入
5 5
1 2 3 4 5
样例输出
3
参考答案
#include <bits/stdc++.h>
using namespace std;
int a[25],n,t,ans;
void dfs(int i,int sum) {
if(i==n) {
if(t==sum) {
ans++;
}
return;
}
i++;
dfs(i,sum+a[i]);
dfs(i,sum);
}
int main() {
cin>>n>>t;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
dfs(0,0);
cout<<ans;
return 0;
}
上一题
下一题