MEDIUM NC#74 Backtracking
90. Subsets II
📖 Problem
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.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Recursive function frames
- •Push/pop state undo
- •Pruning branches early
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply Backtracking reasoning pattern
💡 Approach
- → Sort array to handle duplicates easily
- → Skip duplicates at each level
- → When element equals previous, skip it
- → Time: O(2^n), Space: O(n)
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Sort array to handle duplicates easily
- •Skip duplicates at each level
- •When element equals previous, skip it
Common Pitfalls
- •Time: O(2^n), Space: O(n)
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
subsetsWithDup([1,2,2]); Expected:
[[], [1], [1,2], [1,2,2], [2], [2,2]] Test Case 2
Not run Input:
subsetsWithDup([0]); Expected:
[[], [0]] Test Case 3
Not run Input:
subsetsWithDup([1,1,2,2]); Expected:
[[], [1], [1,1], [1,1,2], [1,1,2,2], [1,2], [1,2,2], [2], [2,2]] 📝 Code Editor
📤 Output