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)
- Initialize Result.
- List to store all combinations.
- Backtrack.
- Try each candidate, recurse with remaining target.
- Base Cases.
- Target = 0: Add combination; Target < 0: Stop.
- 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.
- Initialize DP Array.
- dp[i] holds combinations summing to i.
- Build Combinations.
- For each candidate, add to previous sums.
- 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!