Combination Sum
Problem Description
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
Solve it on LeetCode
Approaches
1. Backtracking
Intuition:
The problem requires us to find all unique combinations of numbers that sum up to a target, allowing unlimited usage of each number. This is a classical combination problem suitable for backtracking, where we try all possibilities and backtrack once we exceed the target or if we've considered the entire list of candidates.
Steps:
- We will sort the input array to help in potential optimizations, although not necessary in this approach.
- Use a recursive backtracking function to explore each combination:
- Include the current candidate in the path and recursively attempt to compute the remaining target.
- If at any point, our current combination sums to the target, save it.
- If the sum exceeds the target, backtrack.
- We avoid duplicates by ensuring each combination is built in non-decreasing order.
Code:
- Time Complexity: O(N^{T/M+1})), where (N) is the number of candidates, (T) is the target value, and (M) is the minimal value among the candidates.
- Space Complexity: O(T/M) for the call stack during the depth of recursion.
2. Backtracking with Pruning
Intuition:
In the previous approach, we performed unnecessary recursive calls even when these calls wouldn't have contributed to a valid combination. By sorting the array initially, we can prune these branches more aggressively and stop processing further once we encounter a candidate larger than the target or the remaining target during recursion.
Steps:
- Begin with sorting the candidates which can make pruning easier.
- While exploring candidates, terminate early if the current candidate exceeds the reduced target at any point, avoiding wasting computation on invalid paths.
- This slight change saves processing time and makes the solution more efficient.
Code:
- Time Complexity: The time complexity remains (O(N^{T/M+1})), but pruning helps in practical scenarios.
- Space Complexity: O(T/M), still for the recursion stack.