Solve Combination Sum with Recursion & Backtracking

Understanding Combination Sum

Solving Combination Sum (Leetcode Problem 39) requires generating all unique combinations where candidate numbers sum to a target. This problem teaches core recursion and backtracking patterns essential for technical interviews. After analyzing this video, I believe the key insight is handling infinite inclusions through strategic index management.

Problem Statement and Example

Given candidates [2,3,5] and target 8, valid combinations are:

[2,2,2,2] (sum=8)
[2,3,3] (sum=8)
[3,5] (sum=8)

Critical constraints:

Same candidate may be reused infinitely
Solutions must be unique combinations

Core Recursion Strategy

Three Choices Per Element

Every element has three possibilities:

Single Inclusion: Add once and move to next index
Multiple Inclusion: Add and reconsider same index
Exclusion: Skip element entirely

def backtrack(index, target, path):
    # Base cases first
    if target == 0: 
        results.append(path.copy())
        return
    if target < 0 or index == len(candidates):
        return
    
    # 1. Single inclusion choice
    path.append(candidates[index])
    backtrack(index + 1, target - candidates[index], path)  # Index increments
    path.pop()
    
    # 2. Multiple inclusion choice
    path.append(candidates[index])
    backtrack(index, target - candidates[index], path)  # Index remains
    path.pop()
    
    # 3. Exclusion choice
    backtrack(index + 1, target, path)  # Target unchanged

Why Backtracking is Crucial

Path manipulation enables state resetting. When exiting recursive branches (after single/multiple inclusions), we remove the last added element using path.pop(). This maintains path integrity for subsequent choices. Forgetting this causes incorrect state propagation - a common interview pitfall.

Key Implementation Details

Base Cases That Terminate Recursion

Target Achieved (target == 0): Valid combination found
Target Exceeded (target < 0): Further additions futile
Index Out-of-Bounds: No more candidates to process

Handling Duplicate Combinations

Since candidates can be reused, we avoid duplicate results using:

results = set()
# Convert path to tuple for hashability
results.add(tuple(sorted(path.copy())))

Time Complexity: Exponential - O(2^N) in worst-case scenarios. Sorting paths before adding to set adds O(KlogK) per combination (K = path length).

Optimization Insights

Early Termination Opportunities

When candidates are sorted, we can break early if candidates[index] > remaining_target:

candidates.sort()  # Pre-sort input
if index < len(candidates) and candidates[index] > target:
    return  # Prune useless branches

Real-World Application

This pattern extends to:

Coin change problems
Subset generation
Permutation problems with repetitions

Actionable Checklist

Sort candidates to enable pruning
Initialize path and results before recursion
Implement three-choice recursion with index management
Remove duplicates via tuple/set conversion
Test edge cases: Empty candidates/target=0

Final Solution Code

def combinationSum(candidates, target):
    def backtrack(start, target, path):
        if target == 0:
            results.add(tuple(sorted(path)))
            return
        if target < 0 or start == len(candidates):
            return
        
        # Single inclusion
        path.append(candidates[start])
        backtrack(start + 1, target - candidates[start], path)
        path.pop()
        
        # Multiple inclusion
        path.append(candidates[start])
        backtrack(start, target - candidates[start], path)
        path.pop()
        
        # Exclusion
        backtrack(start + 1, target, path)
    
    results = set()
    candidates.sort()
    backtrack(0, target, [])
    return [list(comb) for comb in results]

Recommended Practice Resources

Leetcode: Try "Subsets II" (Problem 90) next - builds on these concepts
Book: "The Algorithm Design Manual" by Skiena - excellent backtracking section
Visualizer: Use pythontutor.com for step-by-step recursion visualization

"Mastering backtracking transforms how you approach combinatorial problems." - Senior FAANG Interviewer

When implementing this solution, which base case do you anticipate being most challenging to debug? Share your experience in comments!

Solve Combination Sum with Recursion & Backtracking | DSA Guide