Given a collection of candidate numbers (candidates
) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sum to target
.
Each number in candidates
may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
This problem asks to find all unique combinations of numbers from a given array (candidates
) that sum up to a target value. Each number in candidates
can be used only once. The key to solving this efficiently is to use backtracking with pruning to avoid redundant computations and duplicate combinations.
Sorting: Sort the candidates
array. This allows for easy pruning (explained below) by identifying and skipping duplicate numbers.
Backtracking: A recursive function (dfs
in the code examples) implements backtracking. The function explores all possible combinations by:
candidates
(including the current number in the combination).Pruning: The crucial optimization is pruning. Because the array is sorted:
Time Complexity: In the worst case, the algorithm explores all possible subsets of the input array. The number of subsets is O(2n), where n is the length of candidates
. For each subset, we need to check the sum, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2n). However, the pruning significantly improves the performance in practice. The actual time taken is much less than the worst-case complexity in most instances.
Space Complexity: The space complexity is dominated by the recursion depth and the storage of the result. The maximum recursion depth is O(n) because at most, we can have a combination of all n numbers. The result set can store at most O(2n) combinations in the worst case. Hence, the overall space complexity is O(n + 2n) which simplifies to O(2n) because the exponential term dominates. Again, pruning reduces the space usage in practice.
The provided code examples in various languages demonstrate the algorithm. They all follow the same structure:
candidates
.dfs
function for backtracking with pruning.dfs
to start the search.The core logic within the dfs
function is consistent across all implementations, adapting only to the syntax differences of each programming language. Refer to the code section in the original response for detailed implementations in each of the mentioned languages.