https://leetcode.com/problems/3sum-closest/
#include<algorithm>
using namespace std;
class Solution {
public:
void _sum(vector<int>& nums,int l,int &ans,int target,int x,int n) {
int L=nums.size();
if(n==2){
int r=nums.size()-1;
while(l<r){
if(nums[l]+nums[r]+x>target){
if(abs(ans-target) > abs(nums[l]+nums[r]+x-target)) ans=nums[l]+nums[r]+x;
--r;
}
else if(nums[l]+nums[r]+x<target){
if(abs(ans-target) > abs(nums[l]+nums[r]+x-target)) ans=nums[l]+nums[r]+x;
++l;
}
else{
ans=target;
return ;
}
}
}
else{
for(int i=l;i<=L-n;++i){
if(i!=l && nums[i]==nums[i-1]) continue;
x+=nums[i];
_sum(nums,i+1,ans,target,x,n-1);
if(ans==target) return;
x-=nums[i];
}
}
return;
}
int threeSumClosest(vector<int>& nums, int target) {
/*
对leetcode 15的函数略作修改即可
*/
sort(nums.begin(),nums.end());
int ans=nums[0]+nums[1]+nums[2],x=0;
_sum(nums,0,ans,target,x,3);
return ans;
}
};