c++K个数的和（DFS实例）

题目背景：

从n个数中选取k个数，使他们的和为sum，则选取不同数的方案有几种？
输入格式：

第一行分别为数的总数，选取几个数，和为多少

第二行为这n个数，中间用空格隔开

输出格式：

一个整数，表示有几种选取方案

示例代码一：考虑每个数选或者不选

用到了可行性剪枝，当目前已经选了大于k个数或者目前选取数的总和以及大于了sum明显不行，剪掉这种情况的树枝

#include<iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s)	//i表示当前正在选取第几个数
{								//cnt表示选取了几个数
    							//s表示已选取的数的总和
    //可行性剪枝
    if(cnt > k) return ;
    if(s > sum) return ;
    
	if(i == n)					
	{
		if(cnt == k && s == sum)
		{
			ans++;
		}
		return ;
	}
	dfs(i + 1, cnt, s);	//如果没选取这个数
	dfs(i + 1, cnt + 1, s + a[i]);	//如果选取了这个数
}

int main()
{
	cin >> n >> k >> sum;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	ans = 0;
	dfs(0, 0, 0);
	cout << ans << endl;
    return 0;
}

示例代码二：考虑从剩下的数中选取没选过的

必须用重复性剪枝，否则会出现重复选取的情况，而除以k的阶乘也会让时间复杂度升高不少。

#include<iostream>
using namespace std;
int n, k, sum, cnt, s, ans;
int a[40];
bool xuan[40];
void dfs(int s, int cnt, int pos)
{
    if(s > sum || cnt > k)	//可行性剪枝
    {
		return ;
    }
	if(s == sum && cnt == k)   //边界条件
	{
		ans++;
		return ;
	}
	for (int i = pos; i < n; i++)
	{
		if(!xuan[i])	
		{
			xuan[i] = 1;	
			dfs(s + a[i], cnt + 1, i + 1);	//重复性剪枝，i + 1表示从上一次选取的后面一个位置开始选
			xuan[i] = 0;	
		}
	}
}

int main()
{
	cin >> n >> k >> sum;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	ans = 0;
	dfs(0, 0, 0);	
	cout << ans << endl;
	return 0;
}