Exercise 2: Combination Sum 🎯

Your Task

You are given an array of distinct integers nums and a target integer. Return all unique combinations of numbers from nums that sum to target.

The same number may be chosen unlimited times
Two combinations are the same if the frequency of each chosen number is the same
Return combinations in any order; numbers within each combination can be in any order

Examples

print(combination_sum([2, 5, 6, 9], 9))
# Output: [[2, 2, 5], [9]]
# Explanation: 2+2+5=9, or 9=9

print(combination_sum([3, 4, 5], 16))
# Output: [[3, 3, 3, 3, 4], [3, 3, 5, 5], [4, 4, 4, 4], [3, 4, 4, 5]]

print(combination_sum([3], 5))
# Output: []

The Pattern

For each index, you can:

Include nums[i] (and possibly include it again — stay at index i)
Skip nums[i] (move to index i + 1)

To avoid duplicate combinations like [2,5,2] vs [2,2,5], only consider numbers from the current index onward. When you pick nums[i], recurse starting at i again (to allow reuse). When you skip, move to i + 1.

Hints

Starter Code

def combination_sum(nums, target):
    # Your code here
    pass

# Test your function:
print(combination_sum([2, 5, 6, 9], 9))
# Expected: [[2, 2, 5], [9]]

print(combination_sum([3, 4, 5], 16))
# Expected: [[3, 3, 3, 3, 4], [3, 3, 5, 5], [4, 4, 4, 4], [3, 4, 4, 5]]

print(combination_sum([3], 5))
# Expected: []

Bonus Challenge 🌟

What if each number could only be used once? (Classic "Combination Sum II" — no reuse.)

Hint: When you include nums[i], recurse with start = i + 1 instead of start = i.

Combination Sum