## Saturday, November 15, 2014

### [LeetCode] 4Sum

Given an array S of n integers, are there elements abc, 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:
• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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. k-sum问题可以转化为(k-1)-sum问题：对于数组中每个数A[i]，在A[i+1:n-1]中寻找target-A[i]的(k-1)-sum问题。
2. 直到k=2时，用2sum的双指针扫描来完成。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57``` ```class Solution { public: vector > fourSum(vector &num, int target) { vector> allSol; vector sol; sort(num.begin(),num.end()); kSum(num, 0, num.size()-1, target, 4, sol, allSol); return allSol; } void kSum(vector &num, int start, int end, int target, int k, vector &sol, vector> &allSol) { if(k<=0) return; if(k==1) { for(int i=start; i<=end; i++) { if(num[i]==target) { sol.push_back(target); allSol.push_back(sol); sol.pop_back(); return; } } } if(k==2) { twoSum(num, start, end, target, sol, allSol); return; } for(int i=start; i<=end-k+1; i++) { if(i>start && num[i]==num[i-1]) continue; sol.push_back(num[i]); kSum(num, i+1, end, target-num[i], k-1, sol, allSol); sol.pop_back(); } } void twoSum(vector &num, int start, int end, int target, vector &sol, vector> &allSol) { while(start