Combination Sum
You are given a list of integers numbers (which may include duplicates) and an integer target. Your task is to return all unique combinations of elements from numbers that add up to the given target.
Each number in numbers may only be used once in each combination.
Examples
Input: numbers: [1, 2, 5], target: 5 Output: [[5]] Input: numbers: [2, 2, 2, 2, 2], target: 4 Output: [[2, 2]]
We will use a backtracking solution because:
- We explore all subsets of the list.
- We make decisions to include or skip a number.
- We prune paths early if the current sum exceeds the target.
- We avoid duplicates by skipping repeated numbers at the same recursion level.
Algorithm
Sort the input list: This helps in skipping duplicates later by grouping identical numbers together.
Define a helper backtrack(i, subset):
i is the current index in numbers.
subset is the current combination being built.
Base cases: If sum(subset) == target, we add a copy of the current subset to res.
If i is out of bounds or sum(subset) > target, return.
Choose the number at index i: Append numbers[i] to subset.
Recursively call backtrack(i+1, subset) (move forward and don't reuse the same index).
Pop (backtrack) to undo the choice.
Skip duplicates: After backtracking from numbers[i], skip all duplicates of numbers[i] before the next call.
Don't choose the number at index i: Make a recursive call with backtrack(i+1, subset) to skip the current number.
from typing import List
def combination_sum(numbers: List[int], target: int) -> List[List[int]]:
numbers.sort()
res = []
def backtrack(i, subset):
if sum(subset) == target:
res.append(subset.copy())
return
if i >= len(numbers) or sum(subset) > target:
return
subset.append(numbers[i])
backtrack(i+1, subset)
subset.pop()
while i+1 < len(numbers) and numbers[i] == numbers[i+1]:
i += 1
backtrack(i+1, subset)
backtrack(0, [])
return resTime Complexity: O(2^n) in the worst case as backtracking explores all subsets. The initial sorting step is only O(n log n), but it’s overshadowed by the exponential search. However, pruning and duplicate-skipping reduce unnecessary recursion, making the algorithm much faster on typical inputs even though the theoretical upper bound remains exponential.
Space Complexity: O(n) recursion depth + result storage.