Combination Sum Pattern
What is the Combination Sum Problem?
The Combination Sum problem asks us to find all unique combinations of candidates where the chosen numbers sum to a target.
Each number in the candidates array can be used multiple times in the combination.
Example:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Backtracking Approach
The Combination Sum problem is a perfect example of backtracking:
- Start with an empty combination
- For each candidate, decide whether to include it in the combination
- If including the candidate exceeds the target, skip it
- If including the candidate equals the target, add the combination to the result
- If including the candidate is less than the target, recursively find combinations with the remaining target
- Backtrack by removing the candidate and trying the next one
Implementation
Here's how we can implement the Combination Sum solution using backtracking:
Time and Space Complexity
Time Complexity:
O(2^n * k), where n is the number of candidates and k is the average length of each combination. In the worst case, we explore all possible combinations.
Space Complexity:
O(target), for the recursion stack, plus O(k * x) for storing all combinations, where x is the number of valid combinations.
Pattern 3: Combination Sum
Learn how to solve combinatorial problems using backtracking.
The Combination Sum Problem
The Combination Sum problem asks us to find all unique combinations of candidates where the chosen numbers sum to a target.
Each number in the candidates array can be used multiple times in the combination.
Example:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Explanation:
2 + 2 + 3 = 7
7 = 7
Why Backtracking?
The Combination Sum problem is a perfect candidate for backtracking because:
Combinatorial Nature
We need to find all possible combinations that satisfy a condition.
Incremental Building
We can build combinations one element at a time.
Early Pruning
We can skip candidates that would exceed the target sum.
Multiple Solutions
We need to find all valid combinations, not just one.
Backtracking Approach
1Start Empty
Begin with an empty combination and the full target sum.
2Try Candidates
For each candidate, decide whether to include it in the combination.
3Check Target
If including the candidate equals the target, add the combination to the result.
4Recurse
If including the candidate is less than the target, recursively find combinations with the remaining target.
5Backtrack
Remove the candidate from the combination to try the next one.
6Optimize
Sort candidates and skip those that exceed the target or are duplicates.
Implementation
Here's how we can implement the Combination Sum solution using backtracking:
12345678910111213141516171819202122232425262728293031323334353637383940function combinationSum(candidates, target) { const result = []; // Sort the candidates to help with pruning candidates.sort((a, b) => a - b); function backtrack(start, target, current) { // Base case: target is reached if (target === 0) { result.push([...current]); return; } // Try each candidate for (let i = start; i < candidates.length; i++) { // Skip if the candidate is too large if (candidates[i] > target) { break; } // Skip duplicates if (i > start && candidates[i] === candidates[i - 1]) { continue; } // Include the current candidate current.push(candidates[i]); // Recursively find combinations with the current candidate included // Note: we pass i instead of i+1 because we can reuse the same element backtrack(i, target - candidates[i], current); // Backtrack: remove the current candidate to try the next one current.pop(); } } backtrack(0, target, []); return result;}Time and Space Complexity
Time Complexity
O(2^n * k), where n is the number of candidates and k is the average length of each combination.
In the worst case, we explore all possible combinations. For each candidate, we have two choices: include it or exclude it. The factor k comes from the need to create a copy of the current combination when adding it to the result.
Space Complexity
O(target) for the recursion stack, plus O(k * x) for storing all combinations.
The recursion stack can go up to depth target/min(candidates) in the worst case. Additionally, we need space to store all valid combinations, where x is the number of valid combinations and k is the average length of each combination.