Medium
Combination Sum
👶 The 5-Year-Old Summary
Find numbers that add up to a target! With [2,3,6,7] and target 7, you can use 7 (single) or 2+2+3! Each number can be used unlimited times!
🎮 Interactive Visualizer
Candidates: [2, 3, 6, 7], Target: 7
Valid combinations:
🧠The Brain Hack
Sort, then DFS! Sort candidates to prune branches. If current sum > target, stop! Can reuse same number (don't increment index)!
💻 The Clean Solution
def combination_sum(candidates, target):
result = []
candidates.sort() # Sort for pruning!
def backtrack(start, current, total):
# Found valid combination!
if total == target:
result.append(current[:])
return
# Too big, stop!
if total > target:
return
# Try each candidate
for i in range(start, len(candidates)):
current.append(candidates[i])
backtrack(i, current, total + candidates[i])
current.pop() # Backtrack!
backtrack(0, [], 0)
return result
# [2,3,6,7], target=7 → [[7], [2,2,3]]Time: O branches^depth
Space: O(depth)