LeetCode: 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)

---

The basic idea for this problem is the same as 3Sum. Sort first and then try every combination.

C++ Code:

/*
 * func: four_sum
 * goal: to find four numbers in a vector that can sum up to the
 given target
 * @param num: input number vector
 * @param target: the given target
 * return: all combinations in non-descending order
 */
/*
 * Do in the same way as 3sum
 * complexity: time O(n^3), space O(1)
 */
vector<vector<int> > four_sum_a(vector<int> num, int target){
    vector<vector<int> > result;
    if(num.size() < 4){
        return result;
    }
    sort(num.begin(), num.end());
    int size = static_cast<int>(num.size());
    for(int i = 0; i < size; ++i){
        //Avoid duplicate cases
        if(i != 0 && num[i] == num[i-1]){
            continue;
        }
        for(int j = size-1; j > 0; --j){
            //Avoid duplicate cases
            if(j != size-1 && num[j] == num[j+1]){
                continue;
            }
            
            int left = i+1, right = j-1;
            while(left < right){
                int sum = num[i] + num[left] + num[right] + num[j];
                //Duplicate case
                if(left != i+1 && num[left] == num[left-1]){
                    ++left;
                }else if(right != j-1 && num[right] == num[right+1]){
                    --right;
                }else if(sum > target){
                    --right;
                }else if(sum < target){
                    ++left;
                }else{
                    result.push_back({num[i], num[left], num[right], num[j]});
                    ++left;
                    --right;
                }
            }
        }
    }
    return result;
}

Python Code:

# func: to find 4 numbers in a list that sum up to the target
# @param num: the input list
# @param target: the target value
# @return: all possible combinations
def four_sum(num, target):
    if len(num) < 4:
        return []
    else:
        result = []
        num.sort()
        for first in xrange(len(num)-3):
            if first > 0 and num[first] == num[first-1]:
                continue
            second = len(num) - 1
            while second > first:
                if second != len(num)-1 and num[second] == num[second+1]:
                    second -= 1
                    continue
                third = first+1
                fourth = second-1
                while third < fourth:
                    #Add these to boost so that it can pass large case
                    if num[first] + num[third] + num[third] + num[second] > target:
                        break
                    if num[first] + num[fourth] + num[fourth] + num[second] < target:
                        break
                    sum = num[first] + num[third] + num[fourth] + num[second]
                    if third != first+1 and num[third] == num[third-1]:
                        third += 1
                    elif fourth != second-1 and num[fourth] == num[fourth+1]:
                        fourth -= 1
                    elif sum > target:
                        fourth -= 1
                    elif sum < target:
                        third += 1
                    else:
                        result.append([num[first], num[third], num[fourth], num[second]])
                        third += 1
                        fourth -= 1

                second -= 1
        return result

For the Python code, at first I just translates the code from C++. But it cannot pass large case... So I searched online and found that the code can still be optimized. When the double value of third is larger than target or double value of fourth is smaller than the target, there is no need to perform searching any more. Since all elements behind third is larger than third and elements ahead of fourth is less than fourth. It made me know that I need to keep thinking how to avoid unnecessary calculations all the time. Good lesson.

There is another solution which said can run in O(n^2) times. The idea is keeping all pair values of the elements first and then the problem can be formed to a 2sum problem. The total running time is O(n^2). I tried to implement that but failed. We can keep the pair sum as key and elements indices that form the sum. There is a problem here, if there are multiple pairs of elements that can get the same sum. Then we need to consider every combinations. These will not complete within O(n^2) time. And it will make problem more complicated such as what if there is only one pair sum value after computation? ({0,0,0,0,0,0} and target is 0?)

Reference Link:

1.4Sum - LeetCode: http://discuss.leetcode.com/questions/199/4sum

2.Solution to 4Sum by LeetCode: http://codesays.com/2014/solution-to-4sum-by-leetcode/