39. Combination Sum - Detailed Explanation
Problem Statement
You are given an array of distinct integers called candidates and a target integer target. Your task is to return a list of all unique combinations of candidates where the chosen numbers sum up to target. Each number in candidates may be used an unlimited number of times. The solution set must not contain duplicate combinations.
Examples:
-
Example 1:
- Input:
candidates = [2,3,6,7],target = 7 - Output:
[[2,2,3],[7]] - Explanation:
- 2 + 2 + 3 = 7
- 7 = 7
- Input:
-
Example 2:
- 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
- 3 + 5 = 8
- Input:
Constraints:
- All elements in candidates are distinct.
- The number of candidates is at least 1.
- 1 ≤ candidates.length ≤ 30
- 1 ≤ candidates[i] ≤ 200
- 1 ≤ target ≤ 500
Hints Before Solving
- Hint 1: Since each candidate can be used multiple times, think about a recursive backtracking approach where you can choose the same number repeatedly.
- Hint 2: To avoid duplicate combinations, ensure that you explore candidates in a fixed order and do not revisit previous candidates in the recursive calls.
- Hint 3: Use a helper function that tracks the current combination and the remaining target sum.
Approaches to Solve the Problem
Approach 1: Backtracking (Depth-First Search)
Explanation:
- Idea:
Use recursion (backtracking) to build potential combinations by iterating through the list of candidates. At each step, subtract the candidate’s value from the target and add the candidate to the current combination. If the target reaches zero, a valid combination is found. - Key Points:
- Unlimited Usage: Since each candidate can be used unlimited times, do not advance the index after choosing a candidate.
- Avoiding Duplicates: To avoid duplicate combinations, always process candidates in order and do not go back to previous candidates.
- Steps:
- Start: Begin with an empty list (current combination) and the original target.
- Recursive Call: For each candidate starting from the current index, if it does not exceed the remaining target, include it in the current combination and recursively try to reach the new target (target - candidate).
- Base Case: When the remaining target becomes zero, add a copy of the current combination to the result list.
- Backtrack: Remove the last candidate from the current combination and try the next candidate.
Visual Walkthrough:
Imagine candidates = [2,3,6,7] and target = 7.
- Start with an empty combination
[]and target7. - Choose candidate
2: current combination becomes[2]and new target becomes5.- Choose
2again:[2,2]with target3.- Choose
2again:[2,2,2]with target1→ cannot proceed (1 < 2). - Backtrack; try candidate
3:[2,2,3]with target0→ valid combination found.
- Choose
- Backtrack to
[2]and try candidate3:[2,3]with target2→ cannot sum to 0.
- Choose
- Backtrack to empty combination and try candidate
7:[7]with target0→ valid combination found.
Code Implementations
Python Implementation
Java Implementation
Complexity Analysis
-
Time Complexity:
The worst-case time complexity is exponential. In the worst-case scenario, where the target is small relative to the candidates (or many combinations exist), the backtracking algorithm explores many possible combinations.
Roughly, the time complexity is O(2^(target/min(candidates))) since each candidate can be repeatedly chosen. -
Space Complexity:
O(target/min(candidates)) for the recursion stack in the worst case, plus additional space for storing the current combination.
Since the number of candidates is limited, the extra space is bounded by the maximum depth of recursion.
Step-by-Step Walkthrough
-
Initialization:
- Create an empty list
resultto store valid combinations. - Define a helper function
backtrack(start, currentCombo, remaining).
- Create an empty list
-
Recursive Process:
- For each candidate starting from the current index, check if it can be part of a valid combination (i.e., candidate ≤ remaining).
- Add the candidate to
currentComboand callbacktrackwith updated parameters:- The same
startindex if you want to reuse the candidate. - The new remaining value (
remaining - candidate).
- The same
- If the remaining value becomes 0, add a copy of the current combination to the result.
- After exploring with the candidate, remove it from
currentCombo(backtracking).
-
Completion:
- The recursion ends when all possibilities have been explored.
- Return the
resultcontaining all valid combinations.
Common Mistakes & Edge Cases
-
Common Mistakes:
-
Not allowing the same candidate to be used multiple times.
Make sure to call the recursive function with the same indexiinstead ofi + 1if you want to reuse the candidate. -
Not handling the case where the candidate exceeds the remaining target.
Add a condition to skip candidates larger than the remaining target. -
Forgetting to backtrack (i.e., remove the candidate after the recursive call).
-
-
Edge Cases:
- When target is 0 at the beginning (should return an empty list or list with an empty combination).
- When candidates array is empty (although per constraints, there is at least one candidate).
- When target is smaller than the smallest candidate (should return an empty list).
Alternative Variations and Related Problems
-
Alternative Variation:
Combination Sum II: Each candidate may only be used once. -
Related Problems for Further Practice:
- Subset Sum: Determine if a subset of numbers adds up to a given sum.
- Permutation Problems: Generate permutations of a set of numbers.
- Word Break: A string segmentation problem that also uses backtracking to explore multiple possibilities.
GET YOUR FREE
Coding Questions Catalog
