Combination Sum
Asked at Salesforce
Problem
Given an array of distinct positive integers and a target integer, find all unique combinations where the chosen numbers sum to the target. Each number may be used an unlimited number of times. This is a classic backtracking problem that tests your ability to generate combinations with repetition.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
The key insight: you can reuse elements. At each step, you choose an element and subtract it from the remaining target. If the target reaches 0, you found a valid combination. If it goes negative, backtrack.
To avoid duplicate combinations, always iterate forward from the current index. This ensures [2,3] and [3,2] are not both generated. Start the next recursive call at the same index (not index+1) to allow reuse.
Visual walkthrough for candidates=[2,3,6,7], target=7:
Start: remaining=7, start=0, path=[]
- Choose 2: remaining=5, path=[2]
- Choose 2: remaining=3, path=[2,2]
- Choose 2: remaining=1, path=[2,2,2] -> no candidate <= 1. Backtrack.
- Choose 3: remaining=0, path=[2,2,3]. Found! Save [2,2,3].
- Choose 3: remaining=2, path=[2,3]
- Choose 2: remaining=0, path=[2,3,2]. Found! But [2,3,2] is same as [2,2,3]? No, because after picking 3 (index 1), start=1, so we can pick 3 again but not 2 (index 0 < start=1). Actually we CAN pick 2 at index 1? No,
candidates[1]=3. So from start=1, remaining=2:candidates[1]=3 > 2, break. So [2,3,2] is NOT generated. Good.
- Choose 2: remaining=0, path=[2,3,2]. Found! But [2,3,2] is same as [2,2,3]? No, because after picking 3 (index 1), start=1, so we can pick 3 again but not 2 (index 0 < start=1). Actually we CAN pick 2 at index 1? No,
- Choose 2: remaining=3, path=[2,2]
- Choose 3: remaining=4, path=[3]
- Choose 3: remaining=1 -> no candidate. Backtrack.
- Choose 6: remaining=1 -> no candidate.
- Choose 7: remaining=0, path=[7]. Found!
Result: [[2,2,3], [7]]
Pruning: sort the array. If a candidate is larger than the remaining target, all subsequent candidates are also too large (since the array is sorted). Break early to save time.
Edge cases: empty candidates (return []), target=0 (return [[]] -- empty combination sums to 0), no valid combinations (return []).
Optimal Approach
Step 1: Sort candidates.
Step 2: Use backtracking with parameters: (remaining, start_index, current_path).
Step 3: Base case: if remaining == 0, add path to result.
Step 4: For each candidate from start_index:
- If candidate > remaining, break (sorted, no later candidate works)
- Add candidate to path
- Recurse with (remaining - candidate, same start_index, path)
- Remove candidate from path (backtrack)
Step 5: Return result.
The start_index parameter ensures we generate combinations in sorted order, avoiding duplicates. Allowing the same index means each element can be reused.
Time: O(n^(t/min)) where t = target, min = smallest candidate. Space: O(t/min) for the recursion stack.
What Trips People Up in Real Interviews
Generating duplicate combinations. Without the start index parameter, you'd generate both [2,3] and [3,2]. Always iterate from the current index to avoid reusing earlier elements.
Forgetting that elements can be reused. Each recursive call should pass the same index (not index+1) to allow the same element to be chosen again.
Not pruning when candidate > remaining. After sorting, once a candidate exceeds the remaining target, all subsequent candidates do too. Break early.
Confusing "each number may be used unlimited times" with "each number may be used at most once." If at most once, pass i+1 as the next start index.
Not sorting candidates first. Without sorting, you can't prune by breaking when candidate > remaining. Sorting enables the early termination optimization.
Solution Code
def combinationSum(candidates, target):
result = []
candidates.sort()
def backtrack(remaining, start, path):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(remaining - candidates[i], i, path)
path.pop()
backtrack(target, 0, [])
return resultFrequently Asked Questions
What is the Combination Sum problem?
Given an array of distinct positive integers and a target integer, find all unique combinations where the chosen numbers sum to the target. Each number may be used an unlimited number of times. This is a classic backtracking problem that tests your ability to generate combinations with repetition.
How do you solve Combination Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Combination Sum?
Combination Sum is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on Combination Sum?
- Generating duplicate combinations. Without the `start` index parameter, you'd generate both [2,3] and [3,2]. Always iterate from the current index to avoid reusing earlier elements.
- Forgetting that elements can be reused. Each recursive call should pass the same index (not index+1) to allow the same element to be chosen again.
- Not pruning when candidate > remaining. After sorting, once a candidate exceeds the remaining target, all subsequent candidates do too. Break early.
- Confusing "each number may be used unlimited times" with "each number may be used at most once." If at most once, pass `i+1` as the next start index.
- Not sorting candidates first. Without sorting, you can't prune by breaking when candidate > remaining. Sorting enables the early termination optimization.