018-4sum

Question

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

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: The solution set must not contain duplicate quadruplets.

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]
]

Thought Process

1. Brute Force
   1. Quadruple loop
   2. Time complexity O(n^4)
   3. Space complexity O(1)
2. Recursive solution
   1. Use backtrack to facilitate the process
   2. Finding 4 sum is equivalent of finding 3 sum with current element
   3. Finding 3 sum is equivalent of finding 2 sum with the first element of remaining element
   4. Time complexity O(n^3)
   5. Extra space complexity O(k)

Solution

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) return res;
        Arrays.sort(nums);
        kSum(nums, target, 4, 0, res, new ArrayList<>());
        return res;
    }

    private void kSum(int[] nums, int target, int k, int start, List<List<Integer>> res, List<Integer> path) {
        if (k == 2) {
            int lo = start, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                if (sum < target) {
                    lo++;
                } else if (sum > target) {
                    hi--;
                } else {
                    List<Integer> sol = new ArrayList<>(path);
                    sol.add(nums[lo]);
                    sol.add(nums[hi]);
                    res.add(sol);
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                }
            }
        } else {
            for (int i = start; i <= nums.length - k; i++) {
                // skip the duplicate element
                if (i > start && nums[i] == nums[i - 1]) continue;
                // skip the element that is too small even summing with the k - 1
                // largest element
                if (nums[i] + (k - 1) * nums[nums.length - 1] < target) continue;
                // the remaining element is too big to reach target, skip remaining elements
                if (nums[i] * k > target) break;
                // corner case where the target is multiple of current element
                if (nums[i] * k == target) {
                    if (nums[i + k - 1] == nums[i]) {
                        List<Integer> sol = new ArrayList<>(path);
                        for (int j = 0; j < k; j++) sol.add(nums[i]);
                        res.add(sol);
                    }
                    break;
                }
                path.add(nums[i]);
                kSum(nums, target - nums[i], k - 1, i + 1, res, path);
                path.remove(path.size() - 1);
            }
        }
    }
}

Additional