4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

方法1：递归+剪枝

class Solution { private: bool partition(int left,int right,vector<int>& nums,int val){ while(left <=right){ int middle = left + (right - left )/ 2; if(nums[middle] < val) left = middle + 1; else if(nums[middle] > val) right = middle - 1; else return true; } return false; } void find(int count_num, int index,int temp_sum,int target,vector<int>& buffer,vector<int>& nums,vector<vector<int>>& res){ if(count_num > 4 ) return; else if(count_num == 3){ //two partition int val = target - buffer[0] - buffer[1] - buffer[2]; if(partition(index,nums.size()-1,nums,val)){ buffer.push_back(val); res.push_back(buffer); buffer.pop_back(); } return; } else if(count_num == 4 && temp_sum == target){ res.push_back(buffer); return ; } for(int i = index; i < nums.size(); ++i){ if(i != index && nums[i] == nums[i - 1]) continue; buffer.push_back(nums[i]); find(count_num + 1, i + 1, temp_sum + nums[i],target,buffer,nums,res); buffer.pop_back(); } } public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; vector<int> buffer; if(nums.size() == 0) return res; sort(nums.begin(),nums.end()); find(0,0,0,target,buffer,nums,res); return res; } };

方法2： 非递归+剪枝

class Solution { private: bool two(int left,int right, int val,vector<int>& nums){ while(left <= right){ int middle = left + (right - left )/2; if(nums[middle] < val){ left = middle + 1; } else if(nums[middle] > val){ right = middle - 1; } else return true; } return false; } public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; if(nums.size()<=3) return res; sort(nums.begin(),nums.end()); for(int i = 0 ; i < nums.size()-3; ++i){ if(i!=0 && nums[i] == nums[i-1]) continue; if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) continue; if(nums[i]+nums[nums.size()-1]+nums[nums.size()-2]+nums[nums.size()-3] < target) continue; for(int j = i + 1; j < nums.size()-2; ++j){ if(j!=i+1 && nums[j] == nums[j-1]) continue; int sum_2 = nums[i] + nums[j]; if(sum_2+nums[j+1]+nums[j+2]>target) continue; if(sum_2+nums[nums.size()-1]+nums[nums.size()-2 ]< target) continue; for(int k = j + 1 ; k < nums.size() - 1; ++k){ if(k!=j+1 && nums[k] == nums[k-1]) continue; int sum_3 = nums[i] + nums[j] + nums[k]; if(sum_3 + nums[k+1] > target) continue; if(sum_3 + nums[nums.size() - 1] < target) continue; if(two(k+1,nums.size()-1,target-sum_3,nums)){ res.push_back(vector<int>{nums[i],nums[j],nums[k],target-sum_3}); } } } } return res; } };