4 Sum

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.

Have you met this question in a real interview? 

Yes

Example

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)

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.

public class Solution {

    /**

     * @param numbers : Give an array numbersbers of n integer

     * @param target : you need to find four elements that's sum of target

     * @return : Find all unique quadruplets in the array which gives the sum of

     *           zero.

     */

    public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {     

        //write your code here

        

        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        if(numbers == null || numbers.length <= 3) return res;

        Arrays.sort(numbers);

        for(int i = 0; i < numbers.length - 3; i++){

            if(i > 0 && numbers[i] == numbers[i-1])

                continue;

            for(int j = i + 1; j < numbers.length - 2; j++){    

                if(j > i + 1 && numbers[j] == numbers[j-1])

                    continue;

                int h = j + 1, k = numbers.length - 1;

                while(h < k){

                    if(h > j + 1 && numbers[h] == numbers[h-1]){

                        h++;

                        continue;

                    } 

                    int sum = numbers[i] + numbers[j] + + numbers[h] + numbers[k];

                    if(sum == target){

                        ArrayList<Integer> sub = new ArrayList<Integer>();

                        sub.add(numbers[i]);

                        sub.add(numbers[j]);

                        sub.add(numbers[h]);

                        sub.add(numbers[k]);

                        res.add(sub);

                        h++; k--;

                    } else if(sum > target) k--;

                    else h++;

                }

            }

        }

        return res;

    }

}