LeetCode 39: Combination Sum Solution in Python Explained

Problem Statement

LeetCode 39, Combination Sum, is a medium-level problem where you’re given an array of distinct integers candidates and a target integer target. Your task is to return all unique combinations of numbers from candidates that sum up to target. You can use each number in candidates an unlimited number of times, and the combinations must be unique (order doesn’t matter). Return the result as a list of lists.

Constraints

  • 1 <= candidates.length <= 30: Array length is between 1 and 30.
  • 2 <= candidates[i] <= 40: Each element is between 2 and 40.
  • All elements in candidates are distinct.
  • 1 <= target <= 40: Target is between 1 and 40.

Example

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2+2+3=7 and 7=7 are valid combinations.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: 2+2+2+2=8, 2+3+3=8, and 3+5=8.

Input: candidates = [2], target = 1
Output: []
Explanation: No combination sums to 1.

Understanding the Problem

How do you solve LeetCode 39: Combination Sum in Python? For candidates = [2,3,6,7] and target = 7, find all ways to reach 7 using these numbers (e.g., [2,2,3] and [7]). Numbers can be reused, and we need unique combinations. We’ll explore two approaches: a Backtracking Solution (optimal and primary) and an Alternative with Dynamic Programming (systematic but less intuitive here). The backtracking method builds combinations by exploring possibilities and pruning invalid paths.

Solution 1: Backtracking Approach (Primary)

Explanation

Use backtracking to try combinations, adding numbers to a current combination and reducing the target. If the target becomes 0, a valid combination is found; if negative, backtrack. Start from each candidate and allow reuse by passing the same index forward.

Here’s a flow for [2,3,6,7], target = 7:

Try 2: [2], target = 5 -> [2,2], target = 3 -> [2,2,3], target = 0 (found)
Try 7: [7], target = 0 (found)
  1. Initialize Result.
  • List to store all combinations.
  1. Backtrack.
  • Try each candidate, recurse with remaining target.
  1. Base Cases.
  • Target = 0: Add combination; Target < 0: Stop.
  1. Return Combinations.

Step-by-Step Example

Example 1: candidates = [2,3,6,7], target = 7

We need [[2,2,3], [7]].

  • Goal: Find all combinations summing to 7.
  • Result for Reference: [[2,2,3], [7]].
  • Start: candidates = [2,3,6,7], target = 7, curr = [], result = [].
  • Step 1: Start at index 0 (2).
    • Add 2, curr = [2], target = 5.
    • Add 2, curr = [2,2], target = 3.
    • Add 3, curr = [2,2,3], target = 0, add [2,2,3] to result.
    • Backtrack, curr = [2,2], target = 3, try 6, target = -3, stop.
  • Step 2: Backtrack to curr = [2], try 3, curr = [2,3], target = 2.
    • Try 2, curr = [2,3,2], target = 0 not possible, backtrack.
  • Step 3: Start at index 1 (3), curr = [3], target = 4, no further valid sums.
  • Step 4: Start at index 3 (7), curr = [7], target = 0, add [7].
  • Finish: Return [[2,2,3], [7]].

Example 2: candidates = [2,3,5], target = 8

We need [[2,2,2,2], [2,3,3], [3,5]].

  • Start: result = [].
  • Step 1: Start with 2.
    • [2,2,2,2], target = 0, add to result.
  • Step 2: Start with 2, then 3.
    • [2,3,3], target = 0, add to result.
  • Step 3: Start with 3, then 5.
    • [3,5], target = 0, add to result.
  • Finish: Return [[2,2,2,2], [2,3,3], [3,5]].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    # Line 1: Initialize result
    result = []

    # Line 2: Backtracking helper
    def backtrack(start: int, target: int, curr: list[int]) -> None:
        # Line 3: Base case: target reached
        if target == 0:
            result.append(curr[:])
            return
        # Line 4: Base case: target overshot
        if target < 0:
            return

        # Line 5: Try each candidate from start
        for i in range(start, len(candidates)):
            # Line 6: Add candidate to current combination
            curr.append(candidates[i])
            # Line 7: Recurse with same index (reuse allowed)
            backtrack(i, target - candidates[i], curr)
            # Line 8: Backtrack by removing last addition
            curr.pop()

    # Line 9: Start backtracking
    backtrack(0, target, [])
    # Line 10: Return all combinations
    return result

Alternative: Dynamic Programming Approach

Explanation

Use DP to build combinations bottom-up. For each target value up to target, compute all combinations using candidates. This is less common for this problem but systematic.

  1. Initialize DP Array.
  • dp[i] holds combinations summing to i.
  1. Build Combinations.
  • For each candidate, add to previous sums.
  1. Return dp[target].

Step-by-Step Example (Alternative)

For candidates = [2,3,6,7], target = 7:

  • Start: dp = [[] for _ in range(8)], dp[0] = [[]].
  • Step 1: candidate = 2.
    • dp[2] = [[2]], dp[4] = [[2,2]], dp[6] = [[2,2,2]].
  • Step 2: candidate = 3.
    • dp[3] = [[3]], dp[5] = [[2,3]], dp[6] = [[2,2,2], [3,3]].
  • Step 3: candidate = 7.
    • dp[7] = [[7], [2,2,3]].
  • Finish: dp[7] = [[2,2,3], [7]].

How the Code Works (DP)

def combinationSumDP(candidates: list[int], target: int) -> list[list[int]]:
    # Line 1: Initialize DP array
    dp = [[] for _ in range(target + 1)]
    dp[0] = [[]]  # Base case: empty combination sums to 0

    # Line 2: Process each candidate
    for cand in candidates:
        # Line 3: Build combinations for each sum
        for i in range(cand, target + 1):
            # Line 4: Add current candidate to previous sums
            for combo in dp[i - cand]:
                dp[i].append(combo + [cand])

    # Line 5: Return combinations for target
    return dp[target]

Complexity

  • Backtracking:
    • Time: O(N^(T/M)) – N = len(candidates), T = target, M = min(candidates), exponential due to branching.
    • Space: O(T) – Recursion stack depth.
  • Dynamic Programming:
    • Time: O(N * T * C) – C is average number of combinations per sum.
    • Space: O(T * C) – Storage for all combinations.

Efficiency Notes

Backtracking is more intuitive and practical for this problem, with pruning reducing actual runtime. DP is systematic but memory-intensive due to storing all intermediate combinations.

Key Insights

Tips to master LeetCode 39:

  • Reuse Allowed: Pass same index in backtracking.
  • Target Reduction: Subtract and recurse.
  • Uniqueness: Candidates are distinct, ensuring unique combos.

Additional Example

For candidates = [2,3], target = 6:

  • Goal: [[2,2,2], [3,3]].
  • Backtracking: [2,2,2], [3,3].
  • Result: [[2,2,2], [3,3]].

Edge Cases

  • Target Too Small: [2,3], target = 1 – Return [].
  • Single Candidate: [2], target = 4 – Return [[2,2]].
  • Large Target: [2,3], target = 9 – Return [[2,2,2,3], [2,3,3], [3,3,3]].

Final Thoughts

The Backtracking solution is a star for LeetCode 39 in Python—flexible, efficient, and easy to grasp. For a related challenge, try LeetCode 38: Count and Say to switch gears with sequences! Ready to find some combos? Solve LeetCode 39 on LeetCode now and test it with [2,3,5] or targets like 7 or 10 to perfect your backtracking skills. Dive in and sum it up!