0018. 4Sum

https://leetcode.com/problems/4sum

Description

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n

• a, b, c, and d are distinct.

• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

**Input:** nums = [1,0,-1,0,-2,2], target = 0
**Output:** [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

**Input:** nums = [2,2,2,2,2], target = 8
**Output:** [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200

• -109 <= nums[i] <= 109

• -109 <= target <= 109

ac

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return helper(nums, 0, 4, target);
    }

    private List<List<Integer>> helper(int[] nums, int start, int ksum, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // exit
        if (start >= nums.length) return res;

        if (ksum == 2) {
            int l = start, r = nums.length - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == target) {
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    res.add(tmp);
                    // skip duplicate
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
            return res;
        }

        // recursion
        for (int i = start; i <= nums.length - ksum; i++) {
            if (i > start && nums[i] == nums[i-1]) continue; // skip duplicate
            // child result
            List<List<Integer>> child = helper(nums, i+1, ksum-1, target-nums[i]);
            for (List<Integer> list : child) {
                list.add(nums[i]);
            }
            res.addAll(child);
        }

        return res;
    }
}

/*
sort, recursion till 2sum
*/