One Trick to Solve All N-Sum Problems

Regular LeetCode users are certainly familiar with the famous twoSum problem. Besides twoSum, LeetCode also features 3Sum, 4Sum problems, and it's possible to see 5Sum, 6Sum problems in the future.

In summary, these nSum problems provide you with an array nums and a target sum target, asking you to select n numbers from nums such that their sum equals target.

Is there a good approach to solve these problems systematically? This article will delve into the topic step by step, using a single function to solve all nSum type problems.

To note, for the problems discussed in this article, the C++ code is more concise and easier to understand. Therefore, the code provided here is in C++, and you can translate it into your preferred language.

One, the twoSum Problem

Let's start with a twoSum problem:

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

We can start by sorting nums, then use the two-pointer technique from the previous article Two-Pointer Technique, moving pointers from both ends towards the center:

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 solves the problem. With slight modifications, it can also be applied to LeetCode problem #1 "Two Sum" and problem #167 "Two Sum II - Input Array Is Sorted". I won't write those out here.

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

There may be multiple pairs of elements in nums that sum up to target. Your algorithm should return all unique pairs of elements that sum to target, without any 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: