4Sum

My intuition is derive the solution from 3Sum. Basically, the same idea.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> fourSum(vector<int>& nums, int target) {  
4:      vector<vector<int>> res;  
5:      bool flag = false;  
6:      if (nums.empty()) return res;  
7:      sort(nums.begin(), nums.end());  
8:      for (int i = 0; i < (int)nums.size()-3; i++) {  
9:        if (i > 0 && nums[i] == nums[i-1]) continue;  
10:        int sum3 = target-nums[i];  
11:        flag = false;  
12:        for (int j = i+1; j < (int)nums.size()-2; j++) {  
13:          if (flag && nums[j] == nums[j-1]) continue;  
14:          flag = true;  
15:          int sum2 = sum3-nums[j];  
16:          int start = j+1, end = nums.size()-1;  
17:          while (start < end) {  
18:            if (nums[start]+nums[end]==sum2) {  
19:              vector<int> sol;  
20:              sol.push_back(nums[i]);  
21:              sol.push_back(nums[j]);  
22:              sol.push_back(nums[start++]);  
23:              sol.push_back(nums[end--]);  
24:              res.push_back(sol);  
25:              while (start < end && nums[start] == nums[start-1]) start++;  
26:              while (start < end && nums[end] == nums[end+1]) end--;  
27:            } else if (nums[start]+nums[end]<sum2) {  
28:              start++;  
29:            } else {  
30:              end--;  
31:            }  
32:          }  
33:        }  
34:      }  
35:      return res;  
36:    }  
37:  };