算法笔记8.1.2

#include<iostream>//n个数中取K个数，要求k个数的和=x,如果有多种方案，取方案中，每个数平方后的和的最大的那个方案
#include<vector>
using namespace std;
#define maxn 30
int n, k, x, maxsump = -1, a[maxn];
vector<int>temp, ans;
void DFS(int idex, int nowk, int sum, int sump)
{
	if (idex == x || nowk > k || sum > x)return;
	if (nowk == k && sum == x)
	{
		if (sump > maxsump)
		{
			maxsump = sump;
			ans = temp;
		}
		return;
	}
	temp.push_back(a[idex]);
	DFS(idex + 1, nowk + 1, sum + a[idex], sump + a[idex] * a[idex]);//这里如果说明每个数可以多次选择，则可以改成DFS(idex , nowk + 1, sum + a[idex], sump + a[idex] * a[idex])
	temp.pop_back();
	DFS(idex + 1, nowk, sum , sump );
}
int main()
{
	cin >> n>>x>>k;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	DFS(0, 0, 0, 0);
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	cout << endl;
	return 0;
}