WEEK（3）作业

A-选数问题

问题描述

Given n positive numbers, ZJM can select exactly K of them that sums to S. Now ZJM wonders how many ways to get it!
中文大意：给你n个正数，ZJM能够挑选它们中的K个使他们的和为S。现在ZJM想知道有多少种方法去完成！

Input

The first line, an integer T<=100 indicates the number of test cases. For each case, there are two lines. The first line, three integers indicate n, K and S. The second line, n  integers indicate the positive numbers.

Output

For each case, an integer indicate the answer in a independent line.

样例

Example

Input

1
10 3 10
1 2 3 4 5 6 7 8 9 10

Output

4

Note

Remember that k<=n<=16and all numbers can be stored in 32-bit integer

解题思路

从n个数中选K个，这是一个典型的子集枚举问题，首先可以想到的方法是把所有子集一一列举再判定计数符合要求的子集个数。然而，这种方法并不是最好的，因为我们在枚举过程中会出现大量不合法的枚举判定。那么如何直接跳过这些无效枚举呢？
可以通过设置判定条件提前终止无效枚举。
即当选出的数的个数超过K个，或选出的数的和超过了S时，无论是否向子集中再加入元素没有意义（一定不会合法）。我们可以提前将后续的枚举终止，而不是仍然直到该层枚举到n时才开始递归返回。

代码

#include<iostream>
#include<cstdio>
#include<list>

using namespace std;

int a[20],count=0,n,K,S,T;
list<int> sel;

void search(int i,int sum,list<int> &sel) {
	if(sel.size()==K&&sum==0) {
			count++;
			return;
	}
	if(i==n) return;
	
	//当元素多余K个或选入数总和超过S，枚举终止
	if(sel.size()>K||sum<0) return;
	
	//子集枚举
	search(i+1,sum,sel);//a[i]未被选入，sum不需更新
	sel.push_back(a[i]);
	search(i+1,sum-a[i],sel);//a[i]被选入后，sum需要更新
	sel.pop_back();
} 

int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d",&n,&K,&S);
		for(int i=0;i<n;++i) 
			scanf("%d",a+i);
		search(0,S,sel);
		printf("%d\n",count);

        //一组数据执行结束后清空list，将count置0
		sel.clear();
		count=0;
	}
	return 0;
}