Problem Explanation

The problem asks to find the list of all unique quadruplets from the array that sums up to a certain target. A quadruplet is a group consisting of four elements. The solution must not contain duplicate quadruplets.

For example, given an array [1, 0, -1, 0, -2, 2] and a target as 0, all possible quadruplets are:

• [-1, 0, 0, 1]
• [-2, -1, 1, 2]
• [-2, 0, 0, 2]

Approach

The problem could be solved by using backtracking and two-pointer technique. First, it is better to sort the original array, then use the backtracking idea to iterate through the array for all possible combinations of numbers that can be added to sum up the target. If the iterative variable is large than the current right pointer or if the target is smaller than the multiplication of the current iterative variable and the smallest number in the array, or larger than the multiplication of the iterative variable and the largest number, there is no need to iterate anymore. Otherwise, if the iterative variable equals to 2, we use the two-pointer technique to find two numbers to reach the target. Finally, if the iterative variable is larger than 2, we iterate the array from the current variable to the right pointer, add the current number to the path, and then call the function recursively and then, remove the current number from the path. This process of adding and removing with the help of recursion implements backtracking to find all unique quadruplets from the array that sums up to a certain target.

Python Solution

1
2python
3  class Solution:
4    def fourSum(self, nums, target):
5        nums.sort()
6        results = []
7        self.findNSum(nums, target, 4, [], results)
8        return results
9
10    def findNSum(self, nums, target, N, result, results):
11        if len(nums) < N or N < 2: return
12
13        # solve 2-sum
14        if N == 2:
15            l,r = 0,len(nums)-1
16            while l < r:
17                if nums[l]+nums[r] == target:
18                    results.append(result + [nums[l], nums[r]])
19                    while l < r and nums[l] == nums[l + 1]:
20                        l += 1
21                    while l < r and nums[r] == nums[r - 1]:
22                        r -= 1
23                    l += 1
24                    r -= 1
25                elif nums[l] + nums[r] < target:
26                    l += 1
27                else:
28                    r -= 1
29        else:
30            for i in range(0, len(nums)-N+1):   # careful about range
31                if target < nums[i]*N or target > nums[-1]*N:  # take advantage of sorted list
32                    break
33                if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
34                    self.findNSum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
35        return

Java Solution

1
2java
3class Solution {
4    public List<List<Integer>> fourSum(int[] nums, int target) {
5        Arrays.sort(nums);
6        return kSum(nums, target, 0, 4);
7    }
8    private ArrayList<List<Integer>> kSum(int[] nums, int target, int start, int k) {
9        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
10        if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
11            return res;
12        if (k == 2)
13            return twoSum(nums, target, start);
14        for (int i = start; i < nums.length; ++i)
15            if (i == start || nums[i - 1] != nums[i])
16                for (var set : kSum(nums, target - nums[i], i + 1, k - 1)) {
17                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
18                    res.get(res.size() - 1).addAll(set);
19                }
20        return res;
21    }
22    private ArrayList<List<Integer>> twoSum(int[] nums, int target, int start) {
23        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
24        HashSet<Integer> s = new HashSet<Integer>();
25        for (int i = start; i < nums.length; ++i) {
26            if (res.isEmpty() || res.get(res.size() - 1).get(1) != nums[i])
27                if (s.contains(target - nums[i]))
28                    res.add(Arrays.asList(target - nums[i], nums[i]));
29            s.add(nums[i]);
30        }
31        return res;
32    }
33}

C++ Solution

1
2cpp
3
4class Solution {
5public:
6    vector<vector<int>> fourSum(vector<int>& nums, int target) {
7        vector<vector<int>> ans;
8        vector<int> path;
9        sort(begin(nums), end(nums));
10        nSum(nums, 4, target, 0, nums.size() - 1, path, ans);
11        return ans;
12    }
13
14private:
15    void nSum(const vector<int>& nums, long n, long target, int l, int r,
16              vector<int>& path, vector<vector<int>>& ans) {
17        if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)
18            return;
19        if (n == 2) {
20            while (l < r) {
21                const int sum = nums[l] + nums[r];
22                if (sum == target) {
23                    path.push_back(nums[l]);
24                    path.push_back(nums[r]);
25                    ans.push_back(path);
26                    path.pop_back();
27                    path.pop_back();
28                    ++l;
29                    --r;
30                    while (l < r && nums[l] == nums[l - 1])
31                        ++l;
32                    while (l < r && nums[r] == nums[r + 1])
33                        --r;
34                } else if (sum < target) {
35                    ++l;
36                } else {
37                    --r;
38                }
39            }
40            return;
41        }
42
43        for (int i = l; i <= r; ++i) {
44            if (i > l && nums[i] == nums[i - 1])
45                continue;
46            path.push_back(nums[i]);
47            nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);
48            path.pop_back();
49        }
50    }
51};
52

Please note that due to time constraints, I can only provide solutions in Python, Java and C++. You can easily find solutions for other languages like JavaScript and C# with a simple Google search.## JavaScript Solution

Though the article author hasn't provided a JavaScript solution originally, it is mentioned that it can be obtained with a simple Google search. However, I believe that providing a full solution set in the context would be more beneficial. Therefore, I will provide a JavaScript solution here:

1
2javascript
3var fourSum = function(nums, target) {
4    nums.sort((a, b) => a - b);
5    return kSum(nums, target, 0, 4);
6};
7
8var kSum =  function(nums, target, start, k) {
9        let res = [];
10        if (start === nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
11            return res;
12        if (k === 2)
13            return twoSum(nums, target, start);
14        for (let i = start; i < nums.length; ++i)
15            if (i === start || nums[i - 1] !== nums[i])
16                for (let set of kSum(nums, target - nums[i], i + 1, k - 1)) {
17                    res.push([nums[i], ...set]);
18                }
19        return res;
20    };
21
22var twoSum = function(nums, target, start) {
23        let res = [];
24        let s = new Set();
25        for (let i = start; i < nums.length; ++i) {
26            if (res.length>0 || res[res.length - 1][1] !== nums[i])
27                if (s.has(target - nums[i]))
28                    res.push([target - nums[i], nums[i]]);
29            s.add(nums[i]);
30        }
31        return res;
32    };

The JavaScript solution is relatively the same with the Python, Java and C++ solutions. It just differs in the syntax and language specific methods used.

This completes the solution set for finding all unique quadruplets in an array that add up to a target value in different programming languages including Python, Java, C++ and JavaScript.