Combination Sum II - Solution & Explanation
Problem Statement
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 <= 30
Approach Overview
Problem Overview: Given an integer array candidates and a target value, return all unique combinations where the chosen numbers sum to the target. Each number can be used at most once, and duplicate combinations must be avoided even if the input contains repeated values.
Approach 1: Backtracking with Sorting and Pruning (Time: O(2^n), Space: O(n))
This problem fits naturally with backtracking. Start by sorting the array so duplicates sit next to each other. Recursively build combinations while tracking the remaining target. At each step you iterate forward from the current index, choose a candidate, subtract it from the remaining target, and continue exploring deeper. If the remaining target becomes zero, you record the current path as a valid combination.
The key detail is duplicate elimination. When iterating through candidates, skip elements that are the same as the previous element at the same recursion depth (if i > start and nums[i] == nums[i-1]). Sorting enables this check and prevents generating identical combinations like [1,2,5] multiple times. Another optimization is pruning: once the current number exceeds the remaining target, you stop exploring that branch because further numbers will only be larger.
This approach works well because the search space shrinks quickly after sorting and pruning. The recursion depth is at most n, and the algorithm only explores valid candidate paths instead of brute-forcing every subset.
Approach 2: Dynamic Programming (Time: O(n * target * k), Space: O(n * target))
A dynamic programming variant can also generate combinations that sum to the target. The idea is similar to subset sum. Build a DP table where dp[s] stores combinations that produce sum s. Iterate through the candidates and update the table from target down to the candidate value to ensure each element is used only once.
When updating the table, append the current candidate to combinations that previously formed s - candidate. Because the array may contain duplicates, sorting and careful state handling are required to avoid repeated result sets. While this method systematically builds solutions, it typically consumes more memory because it stores many intermediate combinations.
The DP approach is useful when the target value is relatively small and you want a structured bottom-up solution. However, managing duplicates and combination storage makes it less common in interviews.
Recommended for interviews: The expected solution is the backtracking approach. Interviewers want to see that you recognize the subset-generation pattern, sort the array, skip duplicates, and prune early when the remaining sum becomes negative. A brute-force subset enumeration shows basic understanding, but optimized backtracking with duplicate handling demonstrates strong control of recursion and search pruning. The problem mainly tests skills in array manipulation and recursive exploration.
Approach 1: Backtracking Approach
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.
- The C implementation uses recursion and backtracking to explore each potential combination.
- We sort the array, then use a helper function to check all possible combinations.
- Each time we add a number, we recursively call the backtracking function, updating the target appropriately.
- Duplication is avoided by skipping repeated numbers after sorting.
Complexity
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.
Approach 2: Dynamic Programming Approach
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.
- Dynamic programming solutions lean on maintaining a state to remember results of sub-problems.
- By memoizing previous results, this approach aims to reduce repetitive computations that occur in naive recursive solutions.
Complexity
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 3: Sorting + Pruning + Backtracking
We can first sort the array to facilitate pruning and skipping duplicate numbers.
Next, we design a function dfs(i, s), which means starting the search from index i with a remaining target value of s. Here, i and s are both non-negative integers, the current search path is t, and the answer is ans.
In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If i geq n or s \lt candidates[i], the path is invalid, so we return directly. Otherwise, we start the search from index i, and the search index range is j \in [i, n), where n is the length of the array candidates. During the search, if j \gt i and candidates[j] = candidates[j - 1], it means that the current number is the same as the previous number, we can skip the current number because the previous number has been searched. Otherwise, we add the current number to the search path t, recursively call the function dfs(j + 1, s - candidates[j]), and after the recursion ends, we remove the current number from the search path t.
We can also change the implementation logic of the function dfs(i, s) to another form. If we choose the current number, we add the current number to the search path t, then recursively call the function dfs(i + 1, s - candidates[i]), and after the recursion ends, we remove the current number from the search path t. If we do not choose the current number, we can skip all numbers that are the same as the current number, then recursively call the function dfs(j, s), where j is the index of the first number that is different from the current number.
In the main function, we just need to call the function dfs(0, target) to get the answer.
The time complexity is O(2^n times n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n times n).
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: Sorting + Pruning + Backtracking(Another Form)
We can also change the implementation logic of the function dfs(i, s) to another form. If we choose the current number, we add the current number to the search path t, then recursively call the function dfs(i + 1, s - candidates[i]), and after the recursion ends, we remove the current number from the search path t. If we do not choose the current number, we can skip all numbers that are the same as the current number, then recursively call the function dfs(j, s), where j is the index of the first number that is different from the current number.
The time complexity is O(2^n times n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n times n).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
Complexity Comparison
| 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. |
| Sorting + Pruning + Backtracking | — |
| Sorting + Pruning + Backtracking(Another Form) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Sorting | O(2^n) | O(n) | Best general solution; handles duplicates cleanly with pruning |
| Backtracking with Pruning | O(2^n) worst case but faster in practice | O(n) | Preferred in interviews when the array is sorted and early stopping is possible |
| Dynamic Programming (Subset Sum style) | O(n * target * k) | O(n * target) | Useful when target is small and you want a bottom-up combination-building approach |
Video Solution
L9. Combination Sum II | Leetcode | Recursion | Java | C++ • take U forward • 723,817 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Combination Sum II easy or hard?
Combination Sum II Python/Java solution
How to solve Combination Sum II in O(n)?
What is the best approach for Combination Sum II?
Is Combination Sum II asked at Google/Amazon/Meta?
What data structure is used in Combination Sum II?
What is the time complexity of Combination Sum II?
Ready to solve this problem?
Practice Combination Sum II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor