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 <= 30Problem Overview: Given an array of candidate numbers and a target value, find all unique combinations where the chosen numbers add up to the target. Each number can be used at most once, and the result must not contain duplicate combinations.
Approach 1: Backtracking with Sorting (O(2^n) time, O(n) space)
This problem fits naturally into a backtracking search. Start by sorting the array. Sorting groups equal numbers together, which makes it possible to skip duplicates while exploring combinations. During recursion, iterate through candidates starting from the current index, add the current value to the combination, and recursively search with the remaining target.
The key detail is duplicate handling. When iterating, if candidates[i] == candidates[i-1] and i is not the starting index of the current recursion level, skip that element. This prevents generating the same combination multiple times. The recursion stops when the target becomes zero (valid combination) or negative (invalid path). Because every element is considered once per branch, the worst‑case time complexity is O(2^n), while recursion depth requires O(n) auxiliary space.
This approach is widely used in interview problems involving subset generation with constraints. It is simple, efficient for typical input sizes, and easy to reason about once the duplicate skipping rule is understood.
Approach 2: Dynamic Programming with Combination Tracking (O(n * target * k) time, O(target * k) space)
A dynamic programming variant treats the problem as a constrained subset sum. Maintain a DP structure where dp[s] stores all unique combinations that produce sum s. Process numbers one by one and update sums in descending order so each element is used only once.
For each candidate value num, iterate sums from target down to num. For every combination in dp[s - num], append num and store the result in dp[s]. Because duplicates may exist in the input, sorting and careful set-based filtering are needed to avoid repeated combinations. The complexity depends on how many combinations are generated, represented as k.
This method works well when the target value is relatively small and you want an iterative solution rather than recursion. However, it uses more memory because it stores intermediate combinations for many sums.
Recommended for interviews: The backtracking approach is the one interviewers typically expect. It demonstrates understanding of recursion, pruning, and duplicate handling in sorted arrays. A brute-force subset enumeration shows the basic idea, but optimized backtracking with duplicate skipping shows stronger problem-solving skill and familiarity with common combination generation patterns.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: Typically less than O(2^n) due to repeated subproblem optimization.
Space Complexity: Increases due to cache use and recursive call stack.
| Approach | Complexity |
|---|---|
| Backtracking Approach | 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. |
| Dynamic Programming Approach | Time Complexity: Typically less than O(2^n) due to repeated subproblem optimization. Space Complexity: Increases due to cache use and recursive call stack. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Sorting | O(2^n) | O(n) | General case. Best for interviews and typical constraints where combinations must be enumerated. |
| Dynamic Programming (Combination Tracking) | O(n * target * k) | O(target * k) | When target values are small and an iterative DP formulation is preferred over recursion. |
L9. Combination Sum II | Leetcode | Recursion | Java | C++ • take U forward • 525,378 views views
Watch 9 more video solutions →Practice Combination Sum II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor