深搜经典题目三 选数 题目描述 在n个数里面 选出k个数 是他的总和等于s 样列输入 输入 n k s的值及n个数据
5 2 7 1 2 3 4 5代码输出 输出可行的结果的总数
2基本思路 选择一个数据 接着在选择（或者不选）下一个的数据 直到选出的数据的和等于s 就结束搜索； 代码如下
#include<iostream> using namespace std; int a[1001]; int ans=0; int n,k,s; void dfs(int i,int cnt,int sum){ // n 表示选数的是数组的第几个 //cnt 表示选数的个数 //sum 表示选出来的数的和 if(i==n){ if(cnt==k&&sum==s) { ans++; } return ;//当数据全部搜索一遍之后 结束语句 不在搜索 } dfs(i+1,cnt,sum); //第一数不选 选择下一个数 dfs(i+1,cnt+1,sum+a[i]);//第一个数选 个数加1 sum } int main(){ cin>>n>>k>>s; for(int i=0;i<n;i++) { cin>>a[i]; } dfs(0,0,0); cout<<ans; return 0; }