271. Subsets II
🔗 LeetCode Problem: 90. Subsets II
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking, Bit Manipulation
Problem Statement
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
🌟 ELI5: The Simple Idea!
Think of Subsets I, but with duplicate toppings:
Subsets I (No duplicates):
Toppings: [Cheese, Pepperoni, Mushroom]
All different → All combinations valid
Result: 8 subsets (2³)
Subsets II (With duplicates):
Toppings: [Cheese, Pepperoni, Pepperoni]
↑ ↑
Same topping!
Problem: [Cheese, Pepperoni₁] same as [Cheese, Pepperoni₂]
Solution: When deciding to SKIP or TAKE, if current element
equals previous element AND we're at same decision level,
SKIP it to avoid duplicates!
The Key Insight:
nums = [1, 2, 2]
↑ ↑ ↑
2₁ 2₂ (two 2's)
WITHOUT handling duplicates:
[1, 2₁] and [1, 2₂] → Same subset, appears twice! ✗
WITH handling duplicates:
At each level, if element equals previous element,
and we're not taking it in a sequence,
SKIP to avoid generating duplicate subsets! ✓
🎨 Visual Understanding
The Problem with Duplicates
nums = [1, 2, 2] (unsorted)
Decision tree WITHOUT handling duplicates:
index=0
Consider 1
/ \
SKIP 1 TAKE 1
curr=[] curr=[1]
| |
index=1 index=1
Consider 2₁ Consider 2₁
/ \ / \
SKIP 2₁ TAKE 2₁ SKIP 2₁ TAKE 2₁
curr=[] curr=[2₁] curr=[1] curr=[1,2₁]
| | | |
index=2 index=2 index=2 index=2
Consider Consider Consider Consider
2₂ 2₂ 2₂ 2₂
/ \ / \ / \ / \
[] [2₂] [2₁][2₁,2₂] [1][1,2₂] [1,2₁][1,2₁,2₂]
Result: [[],[2₂],[2₁],[2₁,2₂],[1],[1,2₂],[1,2₁],[1,2₁,2₂]]
↑ ↑ ↑
[2] appears in different forms!
[1,2] appears in different forms!
DUPLICATES! ✗
The Solution: Sort + Skip Duplicates at Same Level
Step 1: SORT the array
nums = [1, 2, 2] → Already sorted
Sorting groups duplicates together:
[1, 2₀, 2₁] (indices 0, 1, 2)
Step 2: Skip duplicates at SAME RECURSION LEVEL
Key Rule:
When making SKIP/TAKE decision at index i:
If nums[i] == nums[i-1] AND we SKIPPED nums[i-1]
→ SKIP nums[i] too!
Why? Because:
- We already explored all subsets without nums[i-1]
- nums[i] == nums[i-1]
→ All subsets without nums[i] are same as without nums[i-1]
→ No need to explore again!
Decision Tree WITH Duplicate Handling
nums = [1, 2, 2] (sorted)
index=0
Consider 1
/ \
SKIP 1 TAKE 1
curr=[] curr=[1]
| |
index=1 index=1
Consider 2₀ Consider 2₀
/ \ / \
SKIP 2₀ TAKE 2₀ SKIP 2₀ TAKE 2₀
curr=[] curr=[2₀] curr=[1] curr=[1,2₀]
| | | |
index=2 index=2 index=2 index=2
Consider Consider Consider Consider
2₁ 2₁ 2₁ 2₁
/ \ / \ / \ / \
At index=2 after SKIP 2₀:
2₁ == 2₀ AND we just SKIPPED 2₀
→ SKIP 2₁ too! (Don't explore)
Final result: [[],[2₀],[2₀,2₁],[1],[1,2₀],[1,2₀,2₁]]
↑ ↑ ↑ ↑
[2] once [2,2] once [1,2] once [1,2,2] once
NO DUPLICATES! ✓
🎨 How Tracking Works - Visual Step by Step
Complete State Tracking for nums=[1,2,2]
Initial: nums = [1, 2, 2] (sorted)
═══════════════════════════════════════════════════════════════
LEVEL 0: index=0, Consider element 1
═══════════════════════════════════════════════════════════════
State:
nums = [1, 2, 2]
index = 0
curr = []
prevSkipped = false (not applicable at index 0)
═══════════════════════════════════════════════════════════════
BRANCH A: SKIP 1
═══════════════════════════════════════════════════════════════
Call: backtrack(nums, 1, [], result, skipped=true)
State:
index = 1
curr = []
prevSkipped = true (we skipped 1)
┌─────────────────────────────────────────┐
│ Path: Skipped 1 │
│ Current subset: [] │
│ Next: Consider 2 at index 1 │
└─────────────────────────────────────────┘
───────────────────────────────────────────────────────────────
SUB-BRANCH A1: SKIP 2 at index 1
───────────────────────────────────────────────────────────────
Call: backtrack(nums, 2, [], result, skipped=true)
State:
index = 2
curr = []
prevSkipped = true (we skipped 2 at index 1)
┌─────────────────────────────────────────┐
│ Path: Skipped 1, Skipped 2 │
│ Current subset: [] │
│ Next: Consider 2 at index 2 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Check: Should we explore SKIP 2 at index 2?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Decision Logic:
nums[2] = 2
nums[1] = 2
nums[2] == nums[1]? YES ✓
Did we SKIP at index 1? YES ✓
→ SKIP this duplicate! Don't explore!
Visualization:
Index 1: [2] → SKIPPED
Index 2: [2] → SKIP TOO (duplicate at same level)
Why? If we skip first 2, skipping second 2 gives
same result (empty set). Already explored!
Skip SKIP branch at index 2 ✓
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
TAKE 2 at index 2 (After skipping 2 at index 1)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
But wait! We can TAKE 2 at index 2 even though we SKIPPED
at index 1, because TAKE creates different subset!
Call: backtrack(nums, 3, [2], result, skipped=false)
State:
index = 3 (end!)
curr = [2]
BASE CASE: Add [2] ✓
Result: [[],[2]]
───────────────────────────────────────────────────────────────
SUB-BRANCH A2: TAKE 2 at index 1
───────────────────────────────────────────────────────────────
Back to index=1, curr=[]
TAKE 2:
Step 2: curr.add(nums[1]) → curr = [2]
Call: backtrack(nums, 2, [2], result, skipped=false)
State:
index = 2
curr = [2]
prevSkipped = false (we TOOK at index 1)
┌─────────────────────────────────────────┐
│ Path: Skipped 1, Took 2 at index 1 │
│ Current subset: [2] │
│ Next: Consider 2 at index 2 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
SKIP 2 at index 2 (After taking 2 at index 1)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Decision Logic:
nums[2] = 2
nums[1] = 2
nums[2] == nums[1]? YES ✓
Did we SKIP at index 1? NO ✗ (we TOOK it!)
→ ALLOW this exploration! Different scenario!
Call: backtrack(nums, 3, [2], result, skipped=true)
BASE CASE: Add [2] ✓ (Wait, already added?)
Actually, this adds [2] again from different path.
We'll handle this by understanding the logic better...
Let me re-explain with the CORRECT approach:
═══════════════════════════════════════════════════════════════
CORRECTED UNDERSTANDING - The Skip Rule
═══════════════════════════════════════════════════════════════
The actual rule is simpler:
At index i, when making SKIP decision:
if (i > start && nums[i] == nums[i-1] && !tookPrevious) {
Skip this SKIP branch!
}
Better way to think:
We don't track "skipped" flag.
Instead, we notice:
- In SKIP branch: don't increment index, so when we come back
to TAKE, we haven't "moved on" from previous element
Actual implementation:
Just ensure when at index i in SKIP path:
If nums[i] == nums[i-1], don't explore
(because SKIP of i-1 already covered this)
Let me show you the cleaner understanding:
═══════════════════════════════════════════════════════════════
CLEANER APPROACH - The Standard Pattern
═══════════════════════════════════════════════════════════════
The standard approach uses a FOR LOOP, not separate SKIP/TAKE calls!
void backtrack(nums, start, curr, result):
Add curr to result
for i = start to nums.length-1:
// Skip duplicates at same level
if (i > start && nums[i] == nums[i-1]):
continue // Skip this iteration
curr.add(nums[i])
backtrack(nums, i+1, curr, result)
curr.remove(last)
This is easier! Let me trace this:
═══════════════════════════════════════════════════════════════
TRACE WITH FOR LOOP APPROACH: nums=[1,2,2]
═══════════════════════════════════════════════════════════════
Call 1: backtrack([1,2,2], start=0, curr=[], result)
Add [] to result ✓
Result: [[]]
Loop i=0: nums[0]=1
Not duplicate (i==start)
curr = [1]
→ backtrack([1,2,2], 1, [1], result)
───────────────────────────────────────────────────────────────
Call 2: backtrack([1,2,2], start=1, curr=[1], result)
Add [1] to result ✓
Result: [[],[1]]
Loop i=1: nums[1]=2
Not duplicate (i==start)
curr = [1,2]
→ backtrack([1,2,2], 2, [1,2], result)
───────────────────────────────────────────────────────────────
Call 3: backtrack([1,2,2], start=2, curr=[1,2], result)
Add [1,2] to result ✓
Result: [[],[1],[1,2]]
Loop i=2: nums[2]=2
Not duplicate (i==start)
curr = [1,2,2]
→ backtrack([1,2,2], 3, [1,2,2], result)
───────────────────────────────────────────────────────────────
Call 4: backtrack([1,2,2], start=3, curr=[1,2,2], result)
Add [1,2,2] to result ✓
Result: [[],[1],[1,2],[1,2,2]]
Loop: start=3 >= length=3, no iterations
Return
───────────────────────────────────────────────────────────────
[Back to Call 3]
Backtrack: curr = [1,2]
Loop finished
Return
[Back to Call 2]
Backtrack: curr = [1]
Loop i=2: nums[2]=2
Check: i > start? YES (2 > 1)
Check: nums[2] == nums[1]? YES (2 == 2)
→ SKIP THIS! (Continue)
┌─────────────────────────────────────────┐
│ CRITICAL: Skipped duplicate! │
│ i=2, start=1, nums[2]==nums[1] │
│ Already explored [1,2,...] from i=1 │
│ No need to explore [1,2,...] from i=2 │
└─────────────────────────────────────────┘
Loop finished
Return
[Back to Call 1]
Backtrack: curr = []
Loop i=1: nums[1]=2
Not duplicate (i > start but diff from previous? No, i=1, start=0)
curr = [2]
→ backtrack([1,2,2], 2, [2], result)
───────────────────────────────────────────────────────────────
Call 5: backtrack([1,2,2], start=2, curr=[2], result)
Add [2] to result ✓
Result: [[],[1],[1,2],[1,2,2],[2]]
Loop i=2: nums[2]=2
Not duplicate (i==start)
curr = [2,2]
→ backtrack([1,2,2], 3, [2,2], result)
───────────────────────────────────────────────────────────────
Call 6: backtrack([1,2,2], start=3, curr=[2,2], result)
Add [2,2] to result ✓
Result: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Return
───────────────────────────────────────────────────────────────
[Back to Call 5]
Backtrack: curr = [2]
Return
[Back to Call 1]
Backtrack: curr = []
Loop i=2: nums[2]=2
Check: i > start? YES (2 > 0)
Check: nums[2] == nums[1]? YES (2 == 2)
→ SKIP THIS! (Continue)
┌─────────────────────────────────────────┐
│ CRITICAL: Skipped duplicate! │
│ Already explored [2,...] from i=1 │
│ No need to explore [2,...] from i=2 │
└─────────────────────────────────────────┘
Loop finished
Return
═══════════════════════════════════════════════════════════════
Final Result: [[],[1],[1,2],[1,2,2],[2],[2,2]]
All unique! No duplicates! ✓
The Key Visualization - When Duplicate is Skipped
At Call 2: start=1, trying elements from index 1 onwards
i=1: nums[1]=2
Check: i > start? NO (1 == 1)
→ Process this ✓
→ Generates: [1,2] and [1,2,2]
i=2: nums[2]=2
Check: i > start? YES (2 > 1) ✓
Check: nums[2] == nums[1]? YES (2 == 2) ✓
→ SKIP! ✗
Why skip?
Already processed nums[1]=2
nums[2] is duplicate of nums[1]
At SAME LEVEL (both children of [1])
Would generate same subsets!
Visual:
[1] → [1,2] → [1,2,2] ✓ (from i=1)
[1] → [1,2] → [1,2,2] ✗ (from i=2, duplicate!)
🎯 Approach 1: Backtracking with For Loop ⭐⭐
The Standard Solution (Easier than Skip/Take!)
Algorithm:
1. SORT the array (crucial!)
2. Use backtracking with FOR LOOP:
- Add current subset
- For each element from start:
- Skip duplicates at same level: if (i > start && nums[i] == nums[i-1])
- Take element, recurse, backtrack
Implementation
import java.util.*;
/**
* Backtracking with duplicate handling
* Time: O(n × 2^n) - Same as Subsets I
* Space: O(n) - Recursion depth
*/
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // CRITICAL: Sort first!
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start,
List<Integer> curr, List<List<Integer>> result) {
// Add current subset
result.add(new ArrayList<>(curr));
// Try adding each element from start onwards
for (int i = start; i < nums.length; i++) {
// Skip duplicates at same recursion level
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Take element
curr.add(nums[i]);
// Recurse
backtrack(nums, i + 1, curr, result);
// Backtrack
curr.remove(curr.size() - 1);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
System.out.println(sol.subsetsWithDup(new int[]{0}));
}
}
⏰ Time: O(n × 2^n) - Generate 2^n subsets, each takes O(n) to copy
💾 Space: O(n) - Maximum recursion depth
⚠️ Common Mistakes
Mistake 1: Not sorting the array
// ❌ WRONG - Can't identify duplicates without sorting!
public List<List<Integer>> subsetsWithDup(int[] nums) {
// No sorting!
backtrack(nums, 0, new ArrayList<>(), result);
}
// nums = [2,1,2] → Can't tell 2's are together!
// ✓ CORRECT - Sort first
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // [1,2,2] now!
backtrack(nums, 0, new ArrayList<>(), result);
}
Mistake 2: Wrong duplicate check condition
// ❌ WRONG - Checks with wrong index
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Would skip [1,2,2] because it blocks 2nd 2 even in path!
// ✓ CORRECT - Check against start
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Only skips at same recursion level, not in path!
Mistake 3: Adding subset at base case instead of every level
// ❌ WRONG - Only adds complete sets
if (start == nums.length) {
result.add(new ArrayList<>(curr));
return;
}
// ✓ CORRECT - Add at every level
result.add(new ArrayList<>(curr));
// Then continue exploring
Mistake 4: Not backtracking properly
// ❌ WRONG - curr keeps growing!
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue;
curr.add(nums[i]);
backtrack(nums, i + 1, curr, result);
// Forgot to remove!
}
// ✓ CORRECT - Remove after recursion
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue;
curr.add(nums[i]);
backtrack(nums, i + 1, curr, result);
curr.remove(curr.size() - 1); // Backtrack!
}
Mistake 5: Using i > 0 instead of i > start
// ❌ WRONG - Blocks duplicates even in same path!
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// For [1,2,2], would generate [1,2] but not [1,2,2]!
// ✓ CORRECT - Only skip at same level
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Allows [1,2,2] in path, skips duplicate at same level
🎯 Pattern Recognition
Problem Type: Subsets with Duplicates
Core Pattern: Backtracking + Sort + Skip Duplicates at Same Level
When to Apply:
✓ Generate all subsets with duplicates
✓ Input may have duplicate values
✓ Must avoid duplicate subsets in result
✓ Power set with duplicates
Recognition Keywords:
- "may contain duplicates"
- "must not contain duplicate subsets"
- "all possible subsets"
- "power set"
Comparison with Related Problems:
┌──────────────────┬────────────┬──────────────┬──────────────┐
│ Problem │ Duplicates │ Skip Logic │ Reuse │
├──────────────────┼────────────┼──────────────┼──────────────┤
│ Subsets │ No │ Not needed │ No │
│ Subsets II │ Yes │ MUST skip! │ No │
│ Combination Sum │ No │ Not needed │ Yes (pass i) │
│ Combination II │ Yes │ MUST skip! │ No (pass i+1)│
└──────────────────┴────────────┴──────────────┴──────────────┘
Key Components:
┌────────────────────────────────────────────┐
│ SORT: Group duplicates together │
│ Skip: if (i > start && arr[i]==arr[i-1]) │
│ Add at every level: Not just base case │
│ For loop: Try elements from start │
│ Time: O(n × 2^n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is Subsets II - has duplicates unlike Subsets I"
Step 2: "Key: SORT first, then skip duplicates at same level"
Step 3: "Use for loop with skip condition: i > start && nums[i] == nums[i-1]"
Key Points to Mention:
- Must sort array first to group duplicates
- Skip duplicates only at same recursion level
- Condition: i > start (not i > 0!)
- Add subset at every level (not just base case)
- Same time complexity as Subsets I
Walk Through Example:
"For nums=[1,2,2]:
Sort: [1,2,2] ✓
Start with []
Try i=0 (1): Add 1
From [1], try i=1 (2): Add 2 → [1,2]
From [1,2], try i=2 (2): Add 2 → [1,2,2] ✓
Back to [1,2], try i=2 (2): SKIP! (i>start && 2==2)
Back to [1], try i=2 (2): SKIP! (i>start && 2==2)
Try i=1 (2): Add 2
From [2], try i=2 (2): Add 2 → [2,2] ✓
Try i=2 (2): SKIP! (i>start && 2==2)
Result: [[],[1],[1,2],[1,2,2],[2],[2,2]]"
Why i > start:
"i > start means we're not at first element of this level.
If nums[i] == nums[i-1] and we're not first,
then we already explored this value at this level.
Example: At level [1], we try i=1 (2) first.
Then we come to i=2 (2) - but it's duplicate!
i > start (2 > 1) and nums[2] == nums[1]
→ Skip to avoid duplicate subsets!"
Complexity:
"Time: O(n × 2^n) - Same as Subsets I
Space: O(n) for recursion depth
Sorting adds O(n log n) but doesn't affect overall"
📝 Quick Revision Notes
🎯 Core Concept:
Subsets II: Like Subsets I but array has duplicates. MUST SORT first to group duplicates. Skip duplicates at same recursion level: if (i > start && nums[i] == nums[i-1]) continue. This prevents generating duplicate subsets like [1,2] twice from two different 2's. Time: O(n × 2^n).
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] a) {
return recursive(a);
}
private List<List<Integer>> recursive(int[] a) {
// Approach:
// Almost same as subsets-i problem
// Main difference is that if we do like and if duplicate
// elements, we can never reach next element.
// In other words, that approach is not possible for duplicates scenario
// So, use for loop
List<List<Integer>> res = new ArrayList<>();
// step 1: sort the array
Arrays.sort(a);
recursive(a, 0, new ArrayList<>(), res);
return res;
}
private void recursive(int[] a, int start, ArrayList<Integer> curr, List<List<Integer>> res) {
// step 7: add every curr to result including empty list
res.add(new ArrayList<>(curr));
// step 2: start at each element starting from index 'start'
for (int i = start; i < a.length; i++) {
// step 3: skipping duplicates
if (i > start && a[i] == a[i - 1]) {
continue;
}
// step 4: add to curr
curr.add(a[i]);
// step 5: proceed to next index
recursive(a, i + 1, curr, res);
// step 6: remove the added element
curr.remove(curr.size() - 1);
}
}
public static void main(String[] args) {
Solution s = new Solution();
// [[],[1],[1,2],[1,2,2],[2],[2,2]]
System.out.println(s.subsetsWithDup(new int[] { 1, 2, 2 }));
// [[],[0]]
System.out.println(s.subsetsWithDup(new int[] { 0 }));
}
}
🔑 Key Insights:
- Pattern: Subsets I + Sort + Skip Duplicates
- MUST SORT: Groups duplicates together
- Skip Condition:
i > start && nums[i] == nums[i-1] - Why i > start: Only skip at same level, not in path
- Allows in path: [1,2,2] valid (both 2's in same path)
- Blocks at level: [1,2] from 2₁ and [1,2] from 2₂ (only first)
- Time: O(n × 2^n), Space: O(n) ✓
🎪 Memory Aid:
"Sort first, skip same level, allow same path!"
"i > start is the key, not i > 0!" ✨
⚠️ Critical Difference - i > start vs i > 0:
Using i > 0 (WRONG):
nums = [1,2,2], sorted
Path: [1]
At level trying to add from index 1:
i=1: nums[1]=2, add it → [1,2]
Now at level trying to add from index 2:
i=2: nums[2]=2
Check: i > 0? YES
Check: nums[2] == nums[1]? YES
→ SKIP!
Result: [1,2] but NOT [1,2,2]! ✗
Blocked 2nd 2 even though it's in SAME PATH!
Using i > start (CORRECT):
nums = [1,2,2], sorted
Path: [1]
At level trying to add from index 1:
i=1: nums[1]=2, add it → [1,2]
Now at level trying to add from index 2:
start=2 (from recursion)
i=2: nums[2]=2
Check: i > start? NO (2 == 2)
→ PROCESS! Add 2 → [1,2,2] ✓
At SAME level from [1]:
i=1: nums[1]=2, explored
i=2: nums[2]=2
Check: i > start? YES (2 > 1)
Check: nums[2] == nums[1]? YES
→ SKIP! (Already explored from i=1)
Result: Both [1,2] and [1,2,2] ✓
🧪 Edge Cases
Case 1: All duplicates
Input: nums = [1,1,1]
Output: [[],[1],[1,1],[1,1,1]]
Each level adds one more 1
Case 2: No duplicates
Input: nums = [1,2,3]
Output: [[],[1],[1,2],[1,2,3],[2],[2,3],[3]]
Same as Subsets I
Case 3: Multiple duplicate sets
Input: nums = [4,4,4,1,4]
After sort: [1,4,4,4,4]
Output: [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],
[4],[4,4],[4,4,4],[4,4,4,4]]
Case 4: Two pairs of duplicates
Input: nums = [1,2,2,3,3]
Output: [[],[1],[1,2],[1,2,2],[1,2,2,3],[1,2,2,3,3],
[1,2,3],[1,2,3,3],[1,3],[1,3,3],
[2],[2,2],[2,2,3],[2,2,3,3],[2,3],[2,3,3],
[3],[3,3]]
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(n × 2^n)
Same as Subsets I!
Why?
Even with duplicates, we generate at most 2^n subsets
(Actually fewer due to duplicates, but big-O is same)
Each subset: O(n) to copy
Total: n × 2^n
Sorting: O(n log n)
But 2^n dominates for n > 4
Example:
n=3: 2³ = 8 max subsets
n=4: 2⁴ = 16 max subsets
n=10: 2¹⁰ = 1024 max subsets
Space Complexity: O(n)
Recursion stack: O(n)
Maximum depth = n
Current list: O(n)
Total: O(n) auxiliary space
Output space: O(n × 2^n) - not counted
📚 Related Problems
Same Core Pattern: - Subsets (LC 78) - Without duplicates (easier) - Combination Sum II (LC 40) - With duplicates + target - Permutations II (LC 47) - Permutations with duplicates
Similar Skip Logic: - Combination Sum II (LC 40) - Same skip pattern! - Permutations II (LC 47) - Same skip pattern! - 3Sum (LC 15) - Skip duplicates in two pointers
Key Learning:
The i > start && arr[i] == arr[i-1] pattern appears in MANY problems with duplicates!
Happy practicing! 🎯
Note: This problem teaches the essential "skip duplicates at same level" technique! The condition i > start && nums[i] == nums[i-1] is crucial for many problems: Combination Sum II, Permutations II, and more. Master the difference between "same level" (skip) and "same path" (allow) and you'll solve all duplicate problems easily! 💪✨