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:

• 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)

----------------------------- thinking -------------------------------
4 sum cannot be implemented as 3 sum closest algorithm !!!!!
Be careful about the duplication in the array!!!
The simple codes is O(n3) complexity

Please read the O(n2) codes in the link
https://oj.leetcode.com/discuss/21401/is-there-really-a-o-n-2-solution

----------------------------- codes -----------------------------------
   class Solution {
   public:
       vector<vector<int> > fourSum(vector<int> &num, int target) {
           sort(num.begin(), num.end());
           vector<vector<int>> result;
           if (num.size() < 4) {
               return result;
           }
           int start = 0;
           int end = num.size() - 1;
           for (int first = 0; first < num.size() - 3; first++) {
               //bug here -> should remove those duplications
               if (first > 0 && num[first] == num[first-1]) {
                      continue;
               }
               //bug here -> the second one should start just next to the first instead of from the end
               //4 sum cannot be fulfilled by the algorithm in 3 sum
               for (int snd = first + 1; snd < num.size() - 2; snd++){
                   //bug here -> should remove those duplications
                   if (snd > first + 1 && num[snd] == num[snd-1]) {
                       continue;
                   }
                   int subsum = target - num[first] - num[snd];
                   int sstart = snd+1;
                   int send = num.size() - 1;
                   while (sstart < send) {
                       if (sstart > snd+1 && num[sstart] == num[sstart - 1]) {
                           sstart++;
                           continue;
                       }
                       if (send < num.size()-1 && num[send] == num[send+1]) {
                           send--;
                           continue;
                       }
                       if (num[sstart] + num[send] == subsum) {
                           int sol[4] = {num[first], num[snd], num[sstart], num[send]};
                           vector<int> sol1(sol, sol+4);
                           result.push_back(sol1);
                           if (num[sstart] == num[send]) {
                               break;
                           }
                           sstart++;
                           send--;
                       } else if (num[sstart] < subsum - num[send]) {
                           sstart++;
                       } else {
                           send--;
                       }
                   }
                   //if (subsum > 0) {
                   //    start++;
                   //} else if (subsum < 0) {
                   //    end--;
                   //} else {
                   //    start++;
                   //    end--;
                   //}
               }
           }
           return result;
       }
   };

------------------------------------ read codes -----------------------------------------
class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        results=set()
        num.sort()
        new_num=[]
        filter=dict()
        for x in num:
            if x not in filter:
                filter[x]=1
                new_num.append(x)
            elif filter[x]<4:
                filter[x]+=1;
                new_num.append(x)
        pairs=[[x,y] for x in xrange(len(new_num)) for y in xrange(x+1,len(new_num))]      
        twoSums=dict()
        for pair in pairs:
            if new_num[pair[0]]+new_num[pair[1]] in twoSums:
                twoSums[new_num[pair[0]]+new_num[pair[1]]].append(pair)
            else:
                twoSums[new_num[pair[0]]+new_num[pair[1]]]=[pair]

        for num1 in twoSums:
            num2=target-num1
            if num2 >= num1 and num2 in twoSums:
                combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2] if pair1[1]<pair2[0]]
                for comb in combinations:
                    results.add(tuple([new_num[i] for i in comb]))
        return [list(sums) for sums in results]