39. Combination Sum
Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 59.7%
Problem Breakdown
Input: A list of distinct positive integers (candidates) and a target integer (target).
Output: A list of lists containing all unique combinations where the sum equals target.
Key Constraints & Rules:
- Unlimited Reuse: Each candidate can be used multiple times in a single combination (e.g.,
[2, 3]is valid if we use2twice). - Unique Combinations: Two combinations are considered different only if the frequency of at least one number differs. Order within a list does not matter for uniqueness; thus,
[2, 3]and[3, 2]count as the same combination. We must generate each unique set exactly once. - Implicit: Since inputs are positive integers (
1 <= candidates[i], target), we do not need to handle negative numbers or zero values incandidates.
Intuition
A brute-force approach would try every possible subset of permutations, which is and includes invalid orderings (e.g., generating [3, 2] after already finding [2, 3]). This leads to massive redundancy.
The key insight for optimization is Backtracking with Index Control.
- We build a combination incrementally by adding candidates one at a time.
- To avoid duplicates (permutations), we enforce an ordering constraint: once we pick
candidates[i], our next recursive step must consider indices . This ensures that if we picked index first, subsequent picks come from the same or later indices in the sorted array, preventing[3, 2]when starting with a smaller number. - Sorting for Pruning: Since candidates are positive integers, sorting them allows us to efficiently prune branches where adding a candidate exceeds
target. If we encounter a value larger than the remaining target, all subsequent values (being sorted) will also be too large, allowing an immediate loop break (break).
Approach
- State: We maintain a recursive function taking
(start_index, current_target). Thecurrent_pathtracks the combination being built. - Preprocessing: Sort the candidates array to enable efficient pruning (early exit from loops when values exceed remaining target). This is computationally cheap () and crucial for correctness of the break optimization on unsorted inputs.
- Base Case: If
current_target == 0, we have found a valid sum; append a copy ofcurrent_pathto results and return (stop this branch). - Recursive Step: Iterate through candidates starting from
start_index. For each candidate:- Check if adding it keeps the remaining target non-negative (
candidate <= current_target). If not, skip or break (since array is sorted) since all subsequent numbers will be larger. - Add candidate to path and recurse with same index (allowing reuse).
- Check if adding it keeps the remaining target non-negative (
- Backtrack: After returning from recursion, remove the last added element from
current_pathso it can try other candidates in this loop iteration.
Complexity Analysis
- Time Complexity: where is the number of candidates and is the maximum depth of valid combinations found (bounded by 150 per constraints). In a theoretical worst case without output limits, it can be exponential relative to
target / min(candidates), but practically bounded here. The sorting step adds negligible overhead (). - Space Complexity: for the recursion stack depth plus space required to store the resulting combinations in memory ().
Solution
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
results = []
# Sort candidates to enable pruning optimization (break loop when value > remaining target)
candidates.sort()
def backtrack(start_index, current_target, path):
# Base Case 1: Target reached exactly
if current_target == 0:
results.append(path[:])
return
# Iterate through candidates starting from start_index to enforce order uniqueness
for i in range(start_index, len(candidates)):
candidate = candidates[i]
# Pruning: If adding this number exceeds target, stop (since array is sorted)
if current_target - candidate < 0:
break
# Choose: Add to path and recurse with same index for unlimited reuse
path.append(candidate)
backtrack(i, current_target - candidate, path)
# Un-choose: Backtrack by removing the last element
path.pop()
backtrack(0, target, [])
return results
# Example usage:
# print(combinationSum([2,3,6,7], 7))
Edge Cases Handled
- Target < Smallest Candidate: The loop condition
current_target - candidate < 0ensures we don’t recurse with negative targets. If no candidates fit the target initially or during recursion, results remain empty ([]). - No Valid Combinations Found: Returns an empty list immediately if base case is never hit.
- Exact Match on Last Step: When
current_target == 0, we append and return correctly without attempting to add more numbers (preventing[2,3]from becoming[2,3, ...]). - Single Candidate Matches Target: The loop runs once, recurses until target is hit or exhausted. If it hits exactly, result contains the single-element list repeated as needed by reuse logic.