1. Problem Statement (Simple Explanation):
You are given:
An array candidates (may contain duplicates).
An integer target.
You must return all unique combinations of numbers from candidates such that:
The sum of the chosen numbers equals target.
Each number can be used at most once in each combination.
The result must not contain duplicate combinations.
Return combinations in any order.
2. Examples:
Example 1:
Input:
candidates = [10,1,2,7,6,1,5]
target = 8
Possible unique combinations:
[1,1,6]
[1,2,5]
[1,7]
[2,6]
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input:
candidates = [2,5,2,1,2]
target = 5
Valid unique combinations:
[1,2,2]
[5]
Output:
[
[1,2,2],
[5]
]
3. Key Differences vs. Combination Sum (Problem 39):
Here, each candidate can be used at most once.
candidates may contain duplicates, but the result must have no duplicate combinations.
We must carefully skip duplicates at the same decision depth.
So the main changes:
We sort candidates.
We move forward with i + 1 when recursing (no reuse).
We skip candidates[i] if it is the same as candidates[i-1] at the same depth.
4. Approach – Backtracking with Sorting and Duplicate Skipping:
Intuition:
Use backtracking (DFS):
Sort candidates so duplicates are adjacent.
At each recursive call, we iterate over indices i from start to end:
If i > start and candidates[i] == candidates[i-1], skip this i (to avoid duplicate combinations starting with the same prefix).
Include candidates[i] once:
Add to current path.
Recurse with start = i + 1 (no reuse).
Backtrack.
We also prune when:
remaining < 0 → stop.
If sorted, we can break when candidates[i] > remaining (optional optimization).
Algorithm (Step-by-Step):
Sort candidates.
Define result list results.
Define backtrack(start, remaining, current):
If remaining == 0:
Add a copy of current to results.
Return.
For i from start to len(candidates)-1:
If i > start and candidates[i] == candidates[i-1]:
continue (skip duplicates at this level).
If candidates[i] > remaining:
break (since further ones will be even larger).
Add candidates[i] to current.
Call backtrack(i + 1, remaining - candidates[i], current) (note i+1, not i).
Remove last element from current (backtrack).
Call backtrack(0, target, []).
Return results.
Pseudo-code:
Let:
n = len(candidates).
Complexity is exponential in general (combinatorial):
Time: worst-case O(2n), but constrained by small target and pruning.
Space:
Recursion depth up to n.
Current combination list up to length n.
So O(n) auxiliary space.
Constraints (target ≤ 30, candidates[i] ≤ 50) keep it practical.
5. Java code:
7. C++ code:
8. Python code:
9. JavaScript code:
Comments
Post a Comment