One Trick to Solve All N-Sum Problems

Frequent LeetCode solvers are surely familiar with the famous twoSum problem. Besides twoSum, there are also 3Sum, 4Sum problems on LeetCode, and hypothetically, 5Sum, 6Sum could appear as well.

In summary, these nSum problems provide an array nums and a target sum target, asking you to select n numbers from nums that add up to target.

Is there a methodical approach to solving such problems? This article will delve into this topic, gradually guiding you through solving all types of nSum problems using a single function.

Note that for the questions discussed in this article, C++ code tends to be more concise and understandable, so all examples provided here will be in C++. You can translate them into your preferred language.

1. TwoSum Problem

Let's start with a twoSum problem:

Given an array nums and a target sum target, return two elements from nums that add up to target. For example, if nums = [1,3,5,6] and target = 9, the algorithm should return the two elements [3,6]. Assume there is exactly one pair of elements that adds up to target.

We can begin by sorting nums and then use the left-right two pointers technique described in 数组双指针技巧汇总 to find the solution by moving inward from both ends:

int[] twoSum(int[] nums, int target) {
    // first sort the array
    Arrays.sort(nums);
    // left and right pointers
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // move the left and right pointers based on the comparison of sum and target
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return new int[]{nums[lo], nums[hi]};
        }
    }
    return new int[]{};
}

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    // first sort the array
    std::sort(nums.begin(), nums.end());
    // left and right pointers
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // move the left and right pointers based on the comparison of sum and target
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return {nums[lo], nums[hi]};
        }
    }
    return {};
}

def twoSum(nums, target):
    # first sort the array
    nums.sort()
    # left and right pointers
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        sum_nums = nums[lo] + nums[hi]
        # move the left and right pointers based on the comparison of sum and target
        if sum_nums < target:
            lo += 1
        elif sum_nums > target:
            hi -= 1
        elif sum_nums == target:
            return [nums[lo], nums[hi]]
    return []

func twoSum(nums []int, target int) []int {
    // first sort the array
    sort.Ints(nums)
    // left and right pointers
    lo, hi := 0, len(nums) - 1
    for lo < hi {
        sum := nums[lo] + nums[hi]
        // move the left and right pointers based on the comparison of sum and target
        if sum < target {
            lo++
        } else if sum > target {
            hi--
        } else if sum == target {
            return []int{nums[lo], nums[hi]}
        }
    }
    return []int{}
}

var twoSum = function(nums, target) {
    // first sort the array
    nums.sort(function(a, b) {return a - b});
    // left and right pointers
    var lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        var sum = nums[lo] + nums[hi];
        // move the left and right pointers based on the comparison of sum and target
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return [nums[lo], nums[hi]];
        }
    }
    return [];
};

This approach can solve the problem, LeetCode problem 1 "Two Sum" and LeetCode problem 167 "Two Sum II - Input Array is Sorted" can be solved with a similar idea with slight modifications, so I won't write them here.

However, I will continue to modify the problem, making it more generalized and a bit more challenging:

There may be multiple pairs of elements in nums whose sum equals target. Your algorithm should return all pairs of elements whose sum is target, ensuring no duplicates.

The function signature is as follows:

List<List<Integer>> twoSumTarget(int[] nums, int target);

vector<vector<int>> twoSumTarget(vector<int>& nums, int target);

def twoSumTarget(nums: List[int], target: int) -> List[List[int]]:

func twoSumTarget(nums []int, target int) [][]int

var twoSumTarget = function(nums, target) {}

For example, if the input is nums = [1,3,1,2,2,3], target = 4, the algorithm returns the result: [[1,3],[2,2]] (note that I require returning elements, not indices).

For the modified problem, the key challenge is that there may be multiple pairs that sum up to target, and they cannot be repeated. For instance, in the above example, [1,3] and [3,1] are considered duplicates and can only be counted once.

First, the basic approach is still sorting plus two pointers: