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.
Here’s the [Problem Link] to begin with.
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
Solution 1: Brute Force Approach (Using Set to Handle Duplicates)
Intuition
Think of this like picking items from a bag where each item can only be picked once, and some items might be identical! Since we can have duplicate numbers in the candidates array, we might generate the same combination multiple times through different paths. For example, if we have and target is 3, we could pick the first 1 and first 2, or first 1 and second 2, both giving . The brute force approach is to generate all possible combinations using standard backtracking and use a set to automatically eliminate duplicates at the end.
Detailed Approach
- Sort the Array: Sort candidates to help with generating combinations in a consistent order.
- Use Set for Results: Use a set to store results as tuples, which automatically handles duplicate combinations.
- Standard Backtracking: For each element, try including it (move to next index) or excluding it (move to next index).
- Base Cases:
- If target equals 0: found a valid combination, add tuple of current subset to set.
- If target becomes negative: invalid path, return.
- If index reaches array end: no more elements to try, return.
- Convert and Return: Convert the set back to a list of lists for the final result.
Code
class Solution:
def backtrack(self, subset: List[int], index: int, target: int, result, candidates):
# Base case: Found a valid combination
if target == 0:
result.add(tuple(subset.copy())) # Add as tuple to set for deduplication
return
# Pruning: Invalid path if target becomes negative
elif target < 0:
return
# Base case: No more candidates to consider
if index >= len(candidates):
return
# Choice 1: Include current candidate
subset.append(candidates[index])
target -= candidates[index]
self.backtrack(subset, index + 1, target, result, candidates) # Move to next index
# Backtrack: Remove the candidate and restore target
subset.pop()
target += candidates[index]
# Choice 2: Exclude current candidate
self.backtrack(subset, index + 1, target, result, candidates)
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort() # Sort to ensure consistent combination generation
result = set() # Use set to automatically handle duplicates
self.backtrack([], 0, target, result, candidates)
return list(result) # Convert set of tuples back to list of listsCode Explanation
This solution uses the classic include/exclude backtracking pattern. We sort the candidates first to ensure that identical combinations are generated in the same order (making deduplication easier). The key insight is using a set to store results as tuples – since tuples are hashable, the set automatically eliminates duplicate combinations. For each candidate, we try including it (subtract from target, move to next index) or excluding it (just move to next index). The backtracking ensures we explore all possibilities, and the set handles the duplicate elimination.
Dry Run
graph TD
Root["backtrack([], 0, 5)<br/>candidates=[1,2,2,2,5]<br/>target=5"]
%% Level 0: index=0, candidate=1
Root --- A["Include 1<br/>subset=[1]<br/>target=4, index=1"]
Root --- B["Exclude 1<br/>subset=[]<br/>target=5, index=1"]
%% Level 1 from Include 1: index=1, candidate=2
A --- A1["Include 2<br/>subset=[1,2]<br/>target=2, index=2"]
A --- A2["Exclude 2<br/>subset=[1]<br/>target=4, index=2"]
%% Level 1 from Exclude 1: index=1, candidate=2
B --- B1["Include 2<br/>subset=[2]<br/>target=3, index=2"]
B --- B2["Exclude 2<br/>subset=[]<br/>target=5, index=2"]
%% Level 2 from [1,2]: index=2, candidate=2
A1 --- A1a["Include 2<br/>subset=[1,2,2]<br/>target=0, index=3"]
A1 --- A1b["Exclude 2<br/>subset=[1,2]<br/>target=2, index=3"]
%% Level 2 from [1]: index=2, candidate=2
A2 --- A2a["Include 2<br/>subset=[1,2]<br/>target=2, index=3"]
A2 --- A2b["Exclude 2<br/>subset=[1]<br/>target=4, index=3"]
%% Level 2 from [2]: index=2, candidate=2
B1 --- B1a["Include 2<br/>subset=[2,2]<br/>target=1, index=3"]
B1 --- B1b["Exclude 2<br/>subset=[2]<br/>target=3, index=3"]
%% Level 2 from []: index=2, candidate=2
B2 --- B2a["Include 2<br/>subset=[2]<br/>target=3, index=3"]
B2 --- B2b["Exclude 2<br/>subset=[]<br/>target=5, index=3"]
%% Level 3 results
A1a --- Success1["target=0<br/>✅ Add (1,2,2) to set"]
A1b --- A1b1["Include 2<br/>subset=[1,2,2]<br/>target=0, index=4"]
A1b --- A1b2["Exclude 2<br/>subset=[1,2]<br/>target=2, index=4"]
A2a --- A2a1["Include 2<br/>subset=[1,2,2]<br/>target=0, index=4"]
A2a --- A2a2["Exclude 2<br/>subset=[1,2]<br/>target=2, index=4"]
A2b --- A2b1["Include 2<br/>subset=[1,2]<br/>target=2, index=4"]
A2b --- A2b2["Exclude 2<br/>subset=[1]<br/>target=4, index=4"]
B1a --- B1a1["Include 2<br/>subset=[2,2,2]<br/>target=-1, index=4"]
B1a --- B1a2["Exclude 2<br/>subset=[2,2]<br/>target=1, index=4"]
B1b --- B1b1["Include 2<br/>subset=[2,2]<br/>target=1, index=4"]
B1b --- B1b2["Exclude 2<br/>subset=[2]<br/>target=3, index=4"]
B2a --- B2a1["Include 2<br/>subset=[2,2]<br/>target=1, index=4"]
B2a --- B2a2["Exclude 2<br/>subset=[2]<br/>target=3, index=4"]
B2b --- B2b1["Include 2<br/>subset=[2]<br/>target=3, index=4"]
B2b --- B2b2["Exclude 2<br/>subset=[]<br/>target=5, index=4"]
%% Level 4 results
A1b1 --- Success2["target=0<br/>✅ Add (1,2,2) to set<br/>(Duplicate - ignored)"]
A2a1 --- Success3["target=0<br/>✅ Add (1,2,2) to set<br/>(Duplicate - ignored)"]
B1a1 --- Fail1["target=-1<br/>❌ Return (pruning)"]
%% Continue with remaining paths that lead to [5]
A2b2 --- A2b2a["Include 5<br/>subset=[1,5]<br/>target=-1, index=5"]
A2b2 --- A2b2b["Exclude 5<br/>subset=[1]<br/>index=5"]
B2b2 --- B2b2a["Include 5<br/>subset=[5]<br/>target=0, index=5"]
B2b2 --- B2b2b["Exclude 5<br/>subset=[]<br/>index=5"]
A2b2a --- Fail2["target=-1<br/>❌ Return (pruning)"]
B2b2a --- Success4["target=0<br/>✅ Add (5) to set"]
%% Final result
Success1 --- Result["Final: {(1,2,2), (5)}<br/>Convert to [[1,2,2], [5]]"]
Success4 --- Result
%% Styling
style Success1 fill:#90EE90
style Success2 fill:#90EE90
style Success3 fill:#90EE90
style Success4 fill:#90EE90
style Result fill:#90EE90
style Fail1 fill:#FFB6C1
style Fail2 fill:#FFB6C1
Click here for better visualization.
Time and Space Complexity
- Time Complexity: O(2^n) – We explore 2^n possible combinations in worst case, plus time for set operations
- Space Complexity: O(k) – Where k is the number of unique combinations, plus recursion stack space
Simplifying It
This approach is like trying on all possible outfit combinations and taking photos, then later removing duplicate photos. It’s straightforward but not the most efficient since we generate duplicates and then remove them.
Solution 2: Optimal Approach (Smart Duplicate Avoidance)
Intuition
Instead of generating duplicates and removing them later, why not avoid generating them in the first place? The key insight is that after sorting, duplicate elements are adjacent. When we’re at a position and considering whether to include a number, if it’s the same as the previous number and we didn’t include the previous number in our current path, then including the current number would create a duplicate combination. So we skip it! It’s like having identical items in a bag – once you decide to skip the first copy of an item at a level, you should skip all remaining copies at that same level.
Detailed Approach
- Sort the Array: Sort candidates to group duplicate values together.
- Use For Loop: Instead of include/exclude pattern, use a for loop to try each remaining candidate.
- Skip Duplicates: If
i > indexandcandidates[i] == candidates[i-1], skip this candidate to avoid duplicates. - Early Termination: If
candidates[i] > target, break the loop (since array is sorted, all remaining elements are also > target). - Recursive Call: Include current candidate and recursively solve for remaining target and remaining candidates.
- Backtrack: Remove the candidate after exploring its path.
Code
class Solution:
def backtrack(self, subset, index, target, result, candidates):
# Base case: Found a valid combination
if target == 0:
result.append(subset.copy()) # Add copy to preserve current state
return
# Try each candidate from current index onwards
for i in range(index, len(candidates)):
# Skip duplicates: if current element is same as previous and we're not
# at the starting position, skip it to avoid duplicate combinations
if i > index and candidates[i] == candidates[i - 1]:
continue
# Early termination: if current candidate exceeds target,
# all remaining candidates will also exceed (array is sorted)
if candidates[i] > target:
break
# Include current candidate
subset.append(candidates[i])
self.backtrack(subset, i + 1, target - candidates[i], result, candidates)
# Backtrack: remove the candidate
subset.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort() # Sort to enable duplicate skipping and early termination
result = []
self.backtrack([], 0, target, result, candidates)
return resultCode Explanation
This optimal solution cleverly avoids generating duplicate combinations by skipping duplicate elements at each level of recursion. The condition if i > index and candidates[i] == candidates[i - 1]: continue ensures that we only use the first occurrence of any duplicate value at each recursion level. The for loop approach naturally handles the choice of which elements to include, and the early termination (if candidates[i] > target: break) saves time by stopping as soon as we encounter an element too large for the remaining target.
Dry Run
graph TD
Root["backtrack([], 0, 5)<br/>candidates=[1,2,2,2,5]"]
%% Level 0 branches
Root --- A["i=0: Try 1<br/>subset=[1]"]
Root --- B["i=1: Try 2<br/>subset=[2]"]
Root --- C["i=2,3: Skip<br/>(duplicates)"]
Root --- D["i=4: Try 5<br/>subset=[5]"]
%% Branch A: [1] - Level 1
A --- A1["i=1: Try 2<br/>subset=[1,2]"]
A --- A2["i=2,3: Skip<br/>(duplicates)"]
A --- A3["i=4: Break<br/>(5 > 4)"]
%% Branch A1: [1,2] - Level 2
A1 --- A1a["i=2: Try 2<br/>subset=[1,2,2]"]
A1 --- A1b["i=3: Skip<br/>(duplicate)"]
A1 --- A1c["i=4: Break<br/>(5 > 2)"]
%% Branch A1a: [1,2,2] - Level 3
A1a --- Success1["target=0<br/>✅ [1,2,2]"]
%% Branch B: [2] - Level 1
B --- B1["i=2: Skip<br/>(duplicate)"]
B --- B2["i=3: Try 2<br/>subset=[2,2]"]
B --- B3["i=4: Break<br/>(5 > 3)"]
%% Branch B2: [2,2] - Level 2
B2 --- B2a["i=4: Break<br/>(5 > 1)"]
%% Branch D: [5] - Level 1
D --- Success2["target=0<br/>✅ [5]"]
%% Final Result
Success1 --- Result["Final: [[1,2,2], [5]]"]
Success2 --- Result
%% Styling
style Success1 fill:#90EE90
style Success2 fill:#90EE90
style Result fill:#90EE90
style A2 fill:#FFE4B5
style A1b fill:#FFE4B5
style B1 fill:#FFE4B5
style C fill:#FFE4B5
style A3 fill:#FFB6C1
style A1c fill:#FFB6C1
style B3 fill:#FFB6C1
style B2a fill:#FFB6C1
Time and Space Complexity
- Time Complexity: O(2^n) – Still explores exponential combinations, but with smart pruning
- Space Complexity: O(k) – Where k is the number of unique valid combinations, plus recursion stack
Simplifying It
This approach is like being smart about trying outfit combinations – if you have two identical shirts, and you decide not to wear the first one in a particular combination, you automatically skip the second identical shirt too. This prevents creating duplicate outfits altogether, making it much more efficient.
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Set) | O(2^n) | O(k) | Medium | Understanding the problem |
| Optimal (Smart Skip) | O(2^n) | O(k) | Hard | Production code |
The optimal approach is generally preferred because it avoids generating duplicates in the first place, making it more efficient both in terms of time and space. The brute force approach is easier to understand initially but less elegant.
The key insight for Combination Sum II is handling duplicates intelligently. The optimal solution demonstrates a beautiful technique for avoiding duplicate combinations in backtracking problems – a pattern that appears in many similar problems like Subsets II and Permutations II!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
