欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

week3作业A

程序员文章站 2022-07-09 18:52:55
...

题意:
给定n,k,s及n个数,之后取n个数中的任意k个数,使之相加的和等于s。
input:
第一行输入组数
第二行输入n,k,s
第三行输入n个数据
output:
输出满足题意的数量
sample input:
1
10 3 10
1 2 3 4 5 6 7 8 9 10
sample output:
4
思路:
运用递归的方法进行求解。将调取的需要进行计算判断的数据不断插入到一个容器中。通过容器的含量来判断选取的数据数量。定义一个函数,通过递归调用此函数,当数据还未遍历结束,且调取的数据量小于k且和大于0时,进行一次递归更新i。把遍历的数据放入到存储的数组中,在调用一次递归,i继续加一,sum的值更新为s-压入的数据,在将数据pop掉,如果最后存储数据的容器含量等于k而且sum的值成为0则表示此时容器中的数据组合即为题意的要求,最终输出所有符合题意要求的数量。

代码:

#include<iostream>
#include<algorithm> 
#include<vector>
using namespace std;
int a,b,c,cnn=0;
int v[16];
void f(int i,int sum,vector<int> &cm)
{
 if(cm.size()==b&&sum==0)
 {
  cnn++;
  return ;
 }
 if(i>=a||cm.size()>b||sum<0)
 return;
 f(i+1,sum,cm);
 cm.push_back(v[i]);
 f(i+1,sum-v[i],cm);
 cm.pop_back();
}
int main()
{
 int n;
 cin>>n;
 while(n--)
 {
  cnn=0;
  vector<int> temp;
  cin>>a>>b>>c;
  for(int i=0;i<a;i++)
  {
   cin>>v[i];
  }
  f(0,c,temp);
  cout<<cnn<<endl;
 }
 return 0; 
}