DFS(二)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;
//题目:从n个数中选k个数使得和为x，且平方和最大的一组
//最大平方和为maxSumSqu
int n,k,x,maxSumSqu=-1,A[9999];
int nowK;
//temp存放临时方案，ans存放平方和最大的方案
vector<int> temp,ans;
int sumSqu;
//当前处理index号整数，当前已选整数个数为nowK
//当前已选整数之和为sum，当前已选整数平方和为sumSqu
void DFS(int index,int nowK,int sum,int maxSumSqu){
  if(nowK==k&&sum==x){//找到k个数的和为x
    if(sumSqu>maxSumSqu){
      maxSumSqu=sumSqu;//更新最大平方和
      ans=temp;//更新最优方案
    }
  return;
  }
  //已经处理完n个数，或者超过k个数，后者和超过x，返回
  if(index==n||nowK>k||sum>x)  return;
  //选index号数
  temp.push_back(A[index]);
  DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
  temp.pop_back();
  //不选index号数
  DFS(index+1,nowK,sum,sumSqu);
}