39. Combination Sum
Asked at Salesforce
Difficulty
Medium
Time
O(n^(t/m))
Space
O(t/m)
Pattern
Array
Companies
1
Problem
You are given an array candidates of distinct positive integers and a target integer. Return every unique combination of numbers from candidates whose sum equals target.
You may use the same number as many times as you like. The order of numbers inside a combination does not matter, and the order of the combinations in your answer does not matter either.
Two combinations are considered the same if they use the same numbers the same number of times. For example, [2,2,3] and [2,3,2] are the same combination, so only one of them should appear in the answer. If no combination sums to target, return an empty list.
Pick numbers that add up to the target
Constraints
- ●
1 <= candidates.length <= 30 - ●
2 <= candidates[i] <= 40 - ●
All elements of candidates are distinct. - ●
1 <= target <= 40 - ●
The number of valid combinations is less than 150.
Examples
candidates = [2,3,6,7], target = 7[[2,2,3],[7]]candidates = [2,3,5], target = 8[[2,2,2,2],[2,3,3],[3,5]]candidates = [2], target = 1[]Asked At
1 companies| 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.
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.
Backtracking with a start index
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
O(n^(t/m)) timedef 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 runs in O(n^(t/m)) time and O(t/m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.