19. 4Sum

Published on September 11, 2023

Question

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.

Algorithm

A follow up of 3 sum.

From 3 sum what you can learn? Reduce to 2 sum. So for 4 sum we many want to reduce to 3 sum and then to 2 sum.

So here is a recursive process and the base condition is k == 2.

When k is bigger than 2, we go through all the unvisited numbers and make it a member, and recursive make the target (target - this number), and less number.

Code

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return KSum(nums, target, 4, 0);
    }
    
    private List<List<Integer>> KSum(int[] nums, long target, int k, int i) {
        List<List<Integer>> res = new ArrayList<>();
        if (k == 2) {
            twoSum(res, nums, target, i);
        } else {
            for (int j = i; j < nums.length; j++) {
                List<List<Integer>> temp = KSum(nums, (long) target - (long) nums[j], k - 1, j + 1);
                if (temp != null) { // if temp is null means there is no solution for these number combanation.
                    for (List<Integer> list : temp) {
                        list.add(0, nums[j]);
                    }
                }
                while (j + 1 < nums.length && nums[j] == nums[j + 1]) {
                    j++;
                }
                res.addAll(temp);
            }
        }
        return res;
    }
    
    private void twoSum(List<List<Integer>> res, int[] nums, long target, int i) {
        int lo = i, hi = nums.length - 1;
        while (lo < hi) {
            long num = (long) nums[lo] + (long) nums[hi];
            if (num == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[lo]);
                list.add(nums[hi]);
                res.add(new ArrayList<>(list));
                while (lo + 1 <= hi && nums[lo] == nums[lo + 1]) {
                    lo++;
                }
                while (lo <= hi - 1 && nums[hi] == nums[hi - 1]) {
                    hi--;
                }
                lo++;
                hi--;
            } else if (num > target) {
                hi--;
            } else {
                lo++;
            }
        }
    }
}