Leetcode: Sum Series — Four Sum

4 min readApr 13, 2024

The Four sum problem series is a generic representation of a ksum prroblem where given a target and k where k is the number of elements required to add upto the target, find all possible combinations.

The intuition of this problem relies on the patterns of both Two Sum and Three sum solutions illustrated in their corresponding article links.

Four Sum

Problem Statement: 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
Input1: nums = [1, 0, -1, 0, -2, 2], target = 0
Output1: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Intuition

Brute force — loop the array four times to check for possible quadruplets whose sum equals to the target.
Generalise the solution to solve any ksum problem, i.e. find k numbers that add to the given target(to be discussed in a subsequent section)

# Python Code

def fourSum(nums: list[int], target: int) -> list[list[int]]:
    nums.sort()
    N, quadruplets = len(nums), set()

    for i in range(N):
        for j in range(i + 1, N):
            left, right = j + 1, N- 1
            
            # typical two sum strategy
            while left < right:
                curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
                if curr_sum == target:
                    quadruplets.add((nums[i], nums[j], nums[left], nums[right]))
                    left, right = left + 1, right - 1
                elif curr_sum < target:
                    left += 1 
                else:
                    right -= 1
                    
    return list(quadruplets)

K Sum

Problem Statement: Given an array nums of n integer and k -> number of unique elements required to sum up to the target, return an array [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
Input1: nums = [1, 0, -1, 0, -2, 2], target = 0, k = 4
Output1: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Intuition

In this series, both the three and four sum solutions rely on the two sum strategy to arrive at a solution. We can therefore infer that the two sum solution is known if k = 2 hence forming the base case.
We have to iterate for i = 0...N-K, because 1) with every ith there can be 3 subsequent numbers that can be co-added upto the target, 2) we don’t have to iterate through the entire list since we only need k elements to form a single combination.
When K > 2, we have keep track of current combination to add upto to
the sum during the recursive iteration

# Python Code 

class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        res = set() # only distinct combinations in the result set

        self.ksum(nums, res, combo=[], k=4, start=0, target=target)
        return [list(tup) for tup in res]


    def ksum(self, nums, res, combo, k, start, target):
        if k == 2:
            # typical two-sum solution
            left, right = start, len(nums) - 1
            while left < right:
                curr_sum = nums[left] + nums[right]
                if  curr_sum == target:
                    res.add(tuple(combo + [nums[left], nums[right]]))
                    left, right = left + 1, right - 1
                elif curr_sum < target:
                    left += 1
                else:
                    right -= 1
        else:
            for j in range(start, len(nums) - k + 1):
                self.ksum(
                    nums, res, combo + [nums[j]], k - 1, j + 1, target - nums[j]
                )

Review *

The time complexity — O(n³), space complexity — O(n).
Use backtracking with Two-sum as the base case.

Four Sum II

Problem Statement: Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= a, b, c, d < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example
Input: nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
Output1: 2
Explanation:The two tuples are:

(0,0,0,1) -> nums1[0]+nums2[0]+nums3[0]+nums4[1] = 1+(-2)+(-1)+2 = 0
(1,1,0,0) -> nums1[1]+nums2[1]+nums3[0]+nums4[0] = 2+(-1)+(-1)+0 = 0

Intuition

How can we leverage Two Sum strategy to solve this problem?

Well, we can group the input nums list into twos, i.e.
Get all sums that can be formed by two numbers from the 2 lists.
From those sums, we need to calculate the remainder by combining 2 numbers that form the compliment.

Note: There can be two number combination sum to the same number.

Explanation

Review *

The time complexity — O(nm), space complexity — O(n + m) , where n and m are the lengths of 2 longest input nums
Takeway — Keep record of the frequency num because there can be more than 1 combinations that add up to the same sum.

Note: The article cover image has not correlation to the problem and solutions provided.