选数问题 Gym - 270437C

题意：

给定n个正整数，从中选取K个数，保证这K个数的和是S。求有多少种选择的方法。

Input
第一行输入一个整数T(T<=100)，表示有T个测试样例。对于每个例子，有两行输入，第一行输入三个整数表示n，K，S，第二行输入给定的n个正整数。

Output
对于每个例子，在单独的一行里输出结果，即有多少种选择的方法。

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

Output
4

Note

记住 k<=n<=16 并且所有的数都可以用一个32位的int型存储。

思路：

这道选数题，从n个数字里面选择K个来达到和为S，为了找出总共有多少种方法，可以采取DFS的思想。DFS的思想是为了得到问题的解，我们先在父节点处选择一种特殊情况，由这种情况继续向前探索，如果发现原来的选则不符合要求或是这种情况的选择已经符合了最终的要求，则回溯至父节点，在父结点处选择另外一种情况，继续向前探索，这样反复进行，直至遍历完所有的情况。

在这道题中，我们设立一个递归函数用以实现DFS，这个函数的参数是：存有这n个正整数的数组int numbers[n]，现在讨论的节点在数组中的位置now，即讨论的是numbers[now]算不算入这K个加数之中，讨论number[now]之前K个加数还剩下几个名额currest，讨论numbers[now]之前的算入到K个加数之中的数的和result，表现形式是：

void solve(int* numbers,int now,int currest,int result)

而讨论这个数算不算入到加数之中，则是在递归函数内调用自身时，传入的参数的区别，若是算入进去，now变为now+1表示现在讨论下一个数了，currest变为currest-1表示剩下的数少了一个，result变为result +numbers[now]表示新的加数的结果。而不算入进去时只有now变为now+1。如下：

solve(numbers, now + 1, currest, result);  //没选numbers[now]
solve(numbers, now + 1, currest - 1, result + numbers[now]);   //选了numbers[now]

终止情况则设置为剩下的加数的数目为0，这时候判断是否结果是要求的，如果是则表示这种方式是正确的，方法数加一，当然当now >= n时表示已经超出了这n个数(位置从0开始)，这时也要返回。

为了减少算法中不必要的探索，即将已经明确知道不符合的情况删除，不再由这种已经错误的情况继续向前探索，需要进行剪枝，这道题目可以设立剪枝条件为结果result已经大于所要求的和，这时候从这种情况就可以返回父节点了。

总结：

对于这种选数问题，可以采用DFS的算法思想解决问题，但是为了减少DFS对不必要情况的探索，需要进行合理的剪枝以优化算法。

代码：

#include<iostream>
using namespace std;
int ways = 0;
int n, k, s;  //n个数，选k个，和为s

void solve(int* numbers,int now,int currest,int result)
{
	if (currest == 0)
	{
		if (result == s)ways++;
		return;
	}
	if (now >= n)return;
	if (result > s)return;

	solve(numbers, now + 1, currest, result);  //没选numbers[now]
	solve(numbers, now + 1, currest - 1, result + numbers[now]);   //选了numbers[now]

}

int main()
{
	int number;
	cin >> number;

	while (number-- != 0)
	{
		cin >> n >> k >> s;
		ways = 0;
		int* numbers = new int[n];
		for (int i = 0; i < n; i++)cin >> numbers[i];
		solve(numbers, 0, k, 0);
		cout << ways << endl;
		delete[]numbers;
	}

}