Finding all unique quadruplets that sums to zero (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. (i.e., a \leq b \leq c \leq d)
  • The solution set must not contain duplicate quadruplets.

INPUT: S = {1, 0, -1, 0, -2, 2}, and target = 0
OUTPUT: (-1, 0, 0, 1), (-2, -1, 1, 2) and (-2, 0, 0, 2)

Thoughts:
The same algorithm as in 3sum. O(n^{3}) algorithm.

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for(int i = 0; i < num.length; ++i) {
            for(int j = i + 1; j < num.length; ++j) {
                int low = j + 1;
                int high = num.length - 1;
                while(low < high) {
                    int sum = num[i] + num[j] + num[low] + num[high];
                    if(sum > target)
                        high--;
                    else if(sum < target)
                        low++;
                    else {
                        ArrayList<Integer> quadruplet = new ArrayList<Integer>();
                        quadruplet.add(num[i]);
                        quadruplet.add(num[j]);
                        quadruplet.add(num[low]);
                        quadruplet.add(num[high]);
                        if(!sol.contains(quadruplet))
                            sol.add(quadruplet);
                        low++;
                        high--;
                    }
                }
            }
        }
        return sol;
    }
}

Code (C++):

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > sol;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size(); ++i) {
            for(int j = i + 1; j < num.size(); ++j) {
                int low = j + 1;
                int high = num.size() - 1;
                while(low < high) {
                    int sum = num[i] + num[j] + num[low] + num[high];
                    if(sum > target)
                        high--;
                    else if(sum < target)
                        low++;
                    else {
                        vector<int> quadruplet(4);
                        quadruplet[0] = num[i];
                        quadruplet[1] = num[j];
                        quadruplet[2] = num[low];
                        quadruplet[3] = num[high];
                        if(find(sol.begin(), sol.end(), quadruplet) == sol.end())
                            sol.push_back(quadruplet);
                        low++;
                        high--;
                    }
                }
            }
        }
        return sol;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: