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 <= 1001 <= candidates[i] <= 501 <= target <= 30Combination Sum II is a classic backtracking problem where you must find all unique combinations of numbers that sum to a target. Each number from the array can be used at most once, and the result must avoid duplicate combinations.
A common strategy is to first sort the array. Sorting helps group duplicate values together and allows you to skip repeated elements during recursion, preventing duplicate combinations in the result.
Using backtracking, you explore candidate numbers while maintaining the remaining target. At each recursive step, you decide whether to include the current number and move forward to the next index. If the remaining target becomes zero, you record the current combination. If it becomes negative, the branch is pruned early.
Carefully skipping duplicate values at the same recursion level is the key insight. This pruning significantly reduces redundant exploration while ensuring all valid unique combinations are found.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Sorting and Duplicate Skipping | O(2^n) in the worst case due to exploring subsets | O(n) recursion depth (excluding result storage) |
take U forward
The primary idea here is to use a backtracking algorithm to explore all potential combinations of numbers that sum up to the target value. By sorting the array first, we can avoid duplicate combinations by skipping over duplicates within the loop. This ensures each combination is unique, as indicated in the problem statement.
Time Complexity: O(2^n) in the worst case, where n is the number of elements in candidates.
Space Complexity: O(n) for recursion stack, where n is the number of elements in the combination.
1#include <stdio.h>
2#include <stdlib.h>
3
4void backtrack(int* candidates, int candidatesSize, int* result, int resultSize,
In this approach, we use a variation of the dynamic programming (DP) paradigm referred to as memoization. Instead of exploring each possibility outright, the DP technique seeks to store the results of previously computed states, allowing reuse and thus reducing redundant calculations. Although it's less intuitive than the backtracking approach, it can provide improved efficiency by leveraging prior knowledge.
This approach may involve defining a recursive function with the current state being a pair of active indices and remaining targets, ensuring we cover all combinations.
Time Complexity: Typically less than O(2^n) due to repeated subproblem optimization.
Space Complexity: Increases due to cache use and recursive call stack.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting groups duplicate elements together, making it easier to skip repeated values during backtracking. This prevents generating duplicate combinations and also enables early pruning when the current value exceeds the remaining target.
Yes, variations of Combination Sum problems frequently appear in technical interviews at large tech companies. They test understanding of recursion, backtracking, pruning techniques, and handling duplicates in combinatorial problems.
The optimal approach uses backtracking combined with sorting. Sorting the array allows you to skip duplicate numbers at the same recursion level, ensuring that only unique combinations are generated while exploring valid sums.
Most solutions use arrays or lists to store the current combination during recursion. A result list stores all valid combinations, while the recursion stack manages exploration of candidate elements.