2Sum and nSum

Question 1

What is the 2Sum problem?

Answer 1

You’re given an array nums and a target value. The goal is to find two numbers that add up to the target. This can be solved either to find just one valid pair or all unique pairs.

Question 2

What’s the most efficient way to solve 2Sum if I only need one pair?

Answer 2

Use a HashMap.

def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i

This gives you one valid pair in O(n) time and O(n) space.

Great for unsorted arrays.

Doesn’t give you all combinations or handle duplicates cleanly.

Question 3

How do I find all unique 2Sum pairs (combinations) instead of just one?

Answer 3

Sort the array and use the two-pointer approach.

def twoSumAll(nums, target):
nums.sort()
res = []
left, right = 0, len(nums) - 1

while left < right:
    total = nums[left] + nums[right]
    if total == target:
        res.append([nums[left], nums[right]])
        while left < right and nums[left] == nums[left + 1]: left += 1
        while left < right and nums[right] == nums[right - 1]: right -= 1
        left += 1
        right -= 1
    elif total < target:
        left += 1
    else:
        right -= 1

return res

Requires sorting, but allows duplicate skipping.

Scales to 3Sum, 4Sum, etc.

Question 4

What is the nSum (or kSum) problem?

Answer 4

It’s a generalized version of 2Sum. You’re trying to find all unique combinations of n numbers that add up to a given target.

Question 5

What strategy is used to solve nSum problems like 3Sum, 4Sum, etc.?

Answer 5

Use a recursive approach where:

You sort the array first.

At each recursive level, you fix one number.

Reduce the problem to (n - 1)Sum on the rest of the array.

Base case is 2Sum, which is solved with the two-pointer method.

Question 6

Why do we sort the array first?

Answer 6

Sorting allows you to:

Use two-pointer logic in the 2Sum base case.

Easily skip over duplicate numbers.

Prune early if the smallest or largest possible sums can’t reach the target.

Ensure your results are in non-decreasing order so combinations aren’t repeated in different orders.

Question 7

What is the start parameter in recursive nSum?

Answer 7

It tracks the current scan position so that:

No number is reused in the same combination.

You always move forward in the array.

You can compare nums[i] == nums[i - 1] to skip duplicates cleanly.

Question 8

What does the full recursive nSum solution look like?

Answer 8

Here’s the complete version using recursion and the two-pointer base case:

class Solution:
def nSum(self, nums, target, n):
nums.sort()
return self.kSum(nums, target, n, 0)

def kSum(self, nums, target, k, start):
    res = []
    if start >= len(nums) or k < 2:
        return res

    if k == 2:
        left, right = start, len(nums) - 1
        while left < right:
            total = nums[left] + nums[right]
            if total == target:
                res.append([nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]: left += 1
                while left < right and nums[right] == nums[right - 1]: right -= 1
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
    else:
        for i in range(start, len(nums) - k + 1):
            if i > start and nums[i] == nums[i - 1]:
                continue
            if nums[i] * k > target:
                break
            if nums[-1] * k < target:
                break
            for subset in self.kSum(nums, target - nums[i], k - 1, i + 1):
                res.append([nums[i]] + subset)
    return res

Question 9

When should I use HashMap vs Two-Pointer for sum problems?

Answer 9

Use HashMap for quick, single-pair lookups in 2Sum.

Use Two-Pointer + Sorting when you need:

All combinations

Duplicate-skipping

Recursive extension to nSum problems