269. Subsets
🔗 LeetCode Problem: 78. Subsets
📊 Difficulty: Medium
🏷️ Topics: Array, Backtracking, Bit Manipulation
Problem Statement
Given an integer array nums of unique elements, 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,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [1,2]
Output: [[],[1],[2],[1,2]]
Example 3:
Input: nums = [0]
Output: [[],[0]]
Constraints:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
🌟 ELI5: The Simple Idea!
Think of choosing toppings for a pizza:
Available toppings: [Cheese, Pepperoni, Mushroom]
For each topping, you decide: SKIP IT or TAKE IT
Topping 1 (Cheese):
SKIP → Move to next topping
TAKE → Add to pizza, move to next topping
All possible pizzas you can make:
1. Skip all → []
2. Take Cheese only → [Cheese]
3. Take Pepperoni only → [Pepperoni]
4. Take Cheese + Pepperoni → [Cheese, Pepperoni]
5. Take Mushroom only → [Mushroom]
6. Take Cheese + Mushroom → [Cheese, Mushroom]
7. Take Pepperoni + Mushroom → [Pepperoni, Mushroom]
8. Take all three → [Cheese, Pepperoni, Mushroom]
Total: 8 pizzas (2³ = 8)
For each element, you have 2 choices:
Element 1: SKIP or TAKE
Element 2: SKIP or TAKE
Element 3: SKIP or TAKE
Total combinations: 2 × 2 × 2 = 8
🎨 Visual Understanding
Decision Tree for nums=[1,2,3]
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 3 Consider 3 Consider 3 Consider 3
/ \ / \ / \ / \
SKIP TAKE SKIP TAKE SKIP TAKE SKIP TAKE
3 3 3 3 3 3 3 3
[] [3] [2] [2,3] [1] [1,3] [1,2] [1,2,3]
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
All 8 subsets! (2³ = 8)
The Pattern - SKIP First, TAKE Second
This is the KEY insight!
At each index, we make TWO recursive calls:
1. FIRST: Skip element → recurse(index + 1)
2. SECOND: Take element → add to curr → recurse(index + 1) → backtrack
Why this order?
- SKIP generates subsets WITHOUT this element
- TAKE generates subsets WITH this element
- Clean separation!
🎨 How Tracking Works - Visual Step by Step
Complete State Tracking for nums=[1,2,3]
═══════════════════════════════════════════════════════════════
LEVEL 0: index=0, Consider element 1
═══════════════════════════════════════════════════════════════
State:
nums = [1, 2, 3]
index = 0 (considering nums[0] = 1)
curr = []
Decision: SKIP 1 or TAKE 1?
═══════════════════════════════════════════════════════════════
BRANCH A: SKIP 1 (First Call)
═══════════════════════════════════════════════════════════════
Call: recursiveUtil(nums, 1, [], res)
State after SKIP:
index = 1 (moved to next)
curr = [] (unchanged)
┌─────────────────────────────────────────┐
│ Path: Skipped 1 │
│ Current subset: [] │
│ Next decision: Element 2 │
└─────────────────────────────────────────┘
───────────────────────────────────────────────────────────────
SUB-BRANCH A1: SKIP 2 (From path: skip 1)
───────────────────────────────────────────────────────────────
Call: recursiveUtil(nums, 2, [], res)
State after SKIP:
index = 2 (moved to next)
curr = [] (unchanged)
┌─────────────────────────────────────────┐
│ Path: Skipped 1, Skipped 2 │
│ Current subset: [] │
│ Next decision: Element 3 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
SKIP 3 (From path: skip 1, skip 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call: recursiveUtil(nums, 3, [], res)
State:
index = 3 (reached end!)
curr = []
BASE CASE: index == nums.length
Add [] to result ✓
Return
Result: [[]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
TAKE 3 (From path: skip 1, skip 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Back to index=2, curr=[]
Now TAKE 3:
Step 2: curr.add(nums[2]) → curr = [3]
Call: recursiveUtil(nums, 3, [3], res)
State:
index = 3 (reached end!)
curr = [3]
BASE CASE: index == nums.length
Add [3] to result ✓
Return
Result: [[], [3]]
Step 3: Backtrack → curr.remove(last) → curr = []
───────────────────────────────────────────────────────────────
SUB-BRANCH A2: TAKE 2 (From path: skip 1)
───────────────────────────────────────────────────────────────
Back to index=1, curr=[]
Now TAKE 2:
Step 2: curr.add(nums[1]) → curr = [2]
Call: recursiveUtil(nums, 2, [2], res)
State:
index = 2
curr = [2]
┌─────────────────────────────────────────┐
│ Path: Skipped 1, Took 2 │
│ Current subset: [2] │
│ Next decision: Element 3 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
SKIP 3 (From path: skip 1, take 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call: recursiveUtil(nums, 3, [2], res)
State:
index = 3 (reached end!)
curr = [2]
BASE CASE: Add [2] to result ✓
Result: [[], [3], [2]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
TAKE 3 (From path: skip 1, take 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Back to index=2, curr=[2]
Now TAKE 3:
Step 2: curr.add(nums[2]) → curr = [2, 3]
Call: recursiveUtil(nums, 3, [2,3], res)
State:
index = 3 (reached end!)
curr = [2, 3]
BASE CASE: Add [2,3] to result ✓
Result: [[], [3], [2], [2,3]]
Step 3: Backtrack → curr = [2]
Back to index=1, curr=[2]
Step 3: Backtrack → curr = []
═══════════════════════════════════════════════════════════════
BRANCH B: TAKE 1 (Second Call from index=0)
═══════════════════════════════════════════════════════════════
Back to index=0, curr=[]
Now TAKE 1:
Step 2: curr.add(nums[0]) → curr = [1]
Call: recursiveUtil(nums, 1, [1], res)
State:
index = 1
curr = [1]
┌─────────────────────────────────────────┐
│ Path: Took 1 │
│ Current subset: [1] │
│ Next decision: Element 2 │
└─────────────────────────────────────────┘
───────────────────────────────────────────────────────────────
SUB-BRANCH B1: SKIP 2 (From path: take 1)
───────────────────────────────────────────────────────────────
Call: recursiveUtil(nums, 2, [1], res)
State:
index = 2
curr = [1]
┌─────────────────────────────────────────┐
│ Path: Took 1, Skipped 2 │
│ Current subset: [1] │
│ Next decision: Element 3 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
SKIP 3 (From path: take 1, skip 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call: recursiveUtil(nums, 3, [1], res)
BASE CASE: Add [1] to result ✓
Result: [[], [3], [2], [2,3], [1]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
TAKE 3 (From path: take 1, skip 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Back to index=2, curr=[1]
TAKE 3:
Step 2: curr.add(nums[2]) → curr = [1, 3]
Call: recursiveUtil(nums, 3, [1,3], res)
BASE CASE: Add [1,3] to result ✓
Result: [[], [3], [2], [2,3], [1], [1,3]]
Step 3: Backtrack → curr = [1]
───────────────────────────────────────────────────────────────
SUB-BRANCH B2: TAKE 2 (From path: take 1)
───────────────────────────────────────────────────────────────
Back to index=1, curr=[1]
TAKE 2:
Step 2: curr.add(nums[1]) → curr = [1, 2]
Call: recursiveUtil(nums, 2, [1,2], res)
State:
index = 2
curr = [1, 2]
┌─────────────────────────────────────────┐
│ Path: Took 1, Took 2 │
│ Current subset: [1, 2] │
│ Next decision: Element 3 │
└─────────────────────────────────────────┘
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
SKIP 3 (From path: take 1, take 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call: recursiveUtil(nums, 3, [1,2], res)
BASE CASE: Add [1,2] to result ✓
Result: [[], [3], [2], [2,3], [1], [1,3], [1,2]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
TAKE 3 (From path: take 1, take 2)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Back to index=2, curr=[1,2]
TAKE 3:
Step 2: curr.add(nums[2]) → curr = [1, 2, 3]
Call: recursiveUtil(nums, 3, [1,2,3], res)
BASE CASE: Add [1,2,3] to result ✓
Result: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
Step 3: Backtrack → curr = [1, 2]
Back to index=1, curr=[1,2]
Step 3: Backtrack → curr = [1]
Back to index=0, curr=[1]
Step 3: Backtrack → curr = []
═══════════════════════════════════════════════════════════════
FINAL RESULT
═══════════════════════════════════════════════════════════════
result = [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
Total: 8 subsets (2³ = 8) ✓
The 3-Step Pattern at Each Level
For each element at index i:
┌──────────────────────────────────────────────────────────────┐
│ Step 1: SKIP - Don't include element │
│ recursiveUtil(nums, index + 1, curr, res) │
│ curr remains unchanged │
│ │
│ Step 2: TAKE - Include element │
│ curr.add(nums[index]) │
│ recursiveUtil(nums, index + 1, curr, res) │
│ │
│ Step 3: BACKTRACK - Restore state │
│ curr.remove(curr.size() - 1) │
│ This undoes the "add" from step 2 │
└──────────────────────────────────────────────────────────────┘
Visual:
index=i, curr=[...]
|
┌───────────┴───────────┐
│ │
SKIP (Step 1) TAKE (Step 2)
curr unchanged curr + element
| |
index=i+1 index=i+1
| |
return return
|
BACKTRACK (Step 3)
curr.remove(last)
Order of Subset Generation
The order subsets are generated (left-to-right DFS):
Index 0, Element 1:
SKIP 1 → generates: [], [3], [2], [2,3]
TAKE 1 → generates: [1], [1,3], [1,2], [1,2,3]
This gives clean separation:
- All subsets WITHOUT 1 come first
- All subsets WITH 1 come after
Visual:
Without 1: [] [3] [2] [2,3]
With 1: [1] [1,3] [1,2] [1,2,3]
🎯 Approach 1: Backtracking (Skip/Take Pattern) ⭐⭐
The Most Intuitive Solution
Algorithm:
At each index:
Step 1: SKIP current element → recurse(index + 1)
Step 2: TAKE current element → add to curr → recurse(index + 1)
Step 3: BACKTRACK → remove from curr
Base case: When index reaches nums.length, add curr to result
Implementation
import java.util.*;
/**
* Backtracking with skip/take pattern
* Time: O(n × 2^n) - 2^n subsets, each takes O(n) to copy
* Space: O(n) - Recursion depth
*/
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int index,
List<Integer> curr, List<List<Integer>> result) {
// Base case: reached end of array
if (index == nums.length) {
result.add(new ArrayList<>(curr));
return;
}
// Step 1: SKIP current element
backtrack(nums, index + 1, curr, result);
// Step 2: TAKE current element
curr.add(nums[index]);
backtrack(nums, index + 1, curr, result);
// Step 3: BACKTRACK - remove added element
curr.remove(curr.size() - 1);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.subsets(new int[]{1,2,3}));
System.out.println(sol.subsets(new int[]{0}));
}
}
⏰ Time: O(n × 2^n) - Generate 2^n subsets, each takes O(n) to copy
💾 Space: O(n) - Maximum recursion depth
🔍 Super Detailed Dry Run
Example: nums = [1,2,3]
Goal: Generate all 8 subsets using skip/take pattern
═══════════════════════════════════════════════════════════════
Call 1: backtrack([1,2,3], index=0, curr=[], result=[])
═══════════════════════════════════════════════════════════════
Not at end (0 < 3)
Step 1: SKIP nums[0]=1
→ backtrack([1,2,3], 1, [], result)
═══════════════════════════════════════════════════════════════
Call 2: backtrack([1,2,3], index=1, curr=[], result=[])
Step 1: SKIP nums[1]=2
→ backtrack([1,2,3], 2, [], result)
───────────────────────────────────────────────────────────────
Call 3: backtrack([1,2,3], index=2, curr=[], result=[])
Step 1: SKIP nums[2]=3
→ backtrack([1,2,3], 3, [], result)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call 4: backtrack([1,2,3], index=3, curr=[], result=[])
BASE CASE: index == 3
Add [] to result ✓
Return
Result: [[]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
[Back to Call 3]
Step 2: TAKE nums[2]=3
curr.add(3) → curr = [3]
→ backtrack([1,2,3], 3, [3], result)
───────────────────────────────────────────────────────────────
Call 5: backtrack([1,2,3], index=3, curr=[3], result=[[]])
BASE CASE: index == 3
Add [3] to result ✓
Return
Result: [[], [3]]
───────────────────────────────────────────────────────────────
[Back to Call 3]
Step 3: BACKTRACK
curr.remove(0) → curr = []
Return
[Back to Call 2]
Step 2: TAKE nums[1]=2
curr.add(2) → curr = [2]
→ backtrack([1,2,3], 2, [2], result)
───────────────────────────────────────────────────────────────
Call 6: backtrack([1,2,3], index=2, curr=[2], result=[[],[3]])
Step 1: SKIP nums[2]=3
→ backtrack([1,2,3], 3, [2], result)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Call 7: backtrack([1,2,3], index=3, curr=[2], result)
BASE CASE: Add [2] to result ✓
Result: [[], [3], [2]]
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
[Back to Call 6]
Step 2: TAKE nums[2]=3
curr.add(3) → curr = [2, 3]
→ backtrack([1,2,3], 3, [2,3], result)
───────────────────────────────────────────────────────────────
Call 8: backtrack([1,2,3], index=3, curr=[2,3], result)
BASE CASE: Add [2,3] to result ✓
Result: [[], [3], [2], [2,3]]
───────────────────────────────────────────────────────────────
[Back to Call 6]
Step 3: BACKTRACK
curr.remove(1) → curr = [2]
Return
[Back to Call 2]
Step 3: BACKTRACK
curr.remove(0) → curr = []
Return
[Back to Call 1]
Step 2: TAKE nums[0]=1
curr.add(1) → curr = [1]
→ backtrack([1,2,3], 1, [1], result)
═══════════════════════════════════════════════════════════════
... (Similar process for taking 1)
Eventually generates: [1], [1,3], [1,2], [1,2,3]
═══════════════════════════════════════════════════════════════
Final Result: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
🎯 Approach 2: Iterative (Building Subsets) ⭐
Alternative Solution
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>()); // Start with empty set
for (int num : nums) {
int size = result.size();
for (int i = 0; i < size; i++) {
List<Integer> newSubset = new ArrayList<>(result.get(i));
newSubset.add(num);
result.add(newSubset);
}
}
return result;
}
How Iterative Works
nums = [1, 2, 3]
Start: [[]]
Add 1:
Existing: [[]]
Create: [[1]] (add 1 to [])
Result: [[], [1]]
Add 2:
Existing: [[], [1]]
Create: [[2], [1,2]] (add 2 to each)
Result: [[], [1], [2], [1,2]]
Add 3:
Existing: [[], [1], [2], [1,2]]
Create: [[3], [1,3], [2,3], [1,2,3]] (add 3 to each)
Result: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Total: 8 subsets ✓
🎯 Approach 3: Bit Manipulation ⭐
Using Binary Representation
Idea: Each subset corresponds to a binary number from 0 to 2^n - 1.
import java.util.*;
/**
* Bit manipulation approach
* Time: O(n × 2^n)
* Space: O(1) - No recursion
*/
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
int totalSubsets = 1 << n; // 2^n
// Generate all numbers from 0 to 2^n - 1
for (int i = 0; i < totalSubsets; i++) {
List<Integer> subset = new ArrayList<>();
// Check each bit
for (int j = 0; j < n; j++) {
// If j-th bit is set, include nums[j]
if ((i & (1 << j)) != 0) {
subset.add(nums[j]);
}
}
result.add(subset);
}
return result;
}
}
How Bit Manipulation Works
nums = [1, 2, 3], n = 3
Generate numbers 0 to 7 (2³ - 1)
Number Binary Bits Set Subset
0 000 none []
1 001 bit 0 [1]
2 010 bit 1 [2]
3 011 bits 0,1 [1,2]
4 100 bit 2 [3]
5 101 bits 0,2 [1,3]
6 110 bits 1,2 [2,3]
7 111 bits 0,1,2 [1,2,3]
Each bit position represents whether to include that element!
Bit mask explanation:
For i = 5 (binary: 101):
j=0: (5 & 1) = 1 → Include nums[0]=1 ✓
j=1: (5 & 2) = 0 → Skip nums[1]=2
j=2: (5 & 4) = 4 → Include nums[2]=3 ✓
Result: [1, 3]
⚠️ Common Mistakes
Mistake 1: Adding before base case instead of at base case
// ❌ WRONG - Adds at every step
result.add(new ArrayList<>(curr));
if (index == nums.length) return;
// Would add partial subsets multiple times!
// ✓ CORRECT - Add only at base case
if (index == nums.length) {
result.add(new ArrayList<>(curr));
return;
}
Mistake 2: Not backtracking after TAKE
// ❌ WRONG - curr keeps growing!
backtrack(nums, index + 1, curr, result); // SKIP
curr.add(nums[index]);
backtrack(nums, index + 1, curr, result); // TAKE
return; // Forgot to remove!
// ✓ CORRECT - Remove after TAKE
backtrack(nums, index + 1, curr, result); // SKIP
curr.add(nums[index]);
backtrack(nums, index + 1, curr, result); // TAKE
curr.remove(curr.size() - 1); // BACKTRACK!
Mistake 3: Wrong order of SKIP and TAKE
// ❌ WRONG - TAKE before SKIP
curr.add(nums[index]); // TAKE first
backtrack(nums, index + 1, curr, result);
curr.remove(curr.size() - 1);
backtrack(nums, index + 1, curr, result); // SKIP second
// Works but order is confusing!
// ✓ CORRECT - SKIP first, TAKE second
backtrack(nums, index + 1, curr, result); // SKIP first
curr.add(nums[index]); // TAKE second
backtrack(nums, index + 1, curr, result);
curr.remove(curr.size() - 1);
Mistake 4: Not copying when adding to result
// ❌ WRONG - All entries point to same list!
if (index == nums.length) {
result.add(curr); // Reference!
return;
}
// ✓ CORRECT - Add a copy
if (index == nums.length) {
result.add(new ArrayList<>(curr));
return;
}
Mistake 5: Using start index like combinations
// ❌ WRONG - This is for combinations, not subsets!
for (int i = start; i < nums.length; i++) {
// Skip/take pattern doesn't need loop!
}
// ✓ CORRECT - Process one element at index
backtrack(nums, index + 1, curr, result); // SKIP
curr.add(nums[index]); // TAKE
backtrack(nums, index + 1, curr, result);
curr.remove(curr.size() - 1);
🎯 Pattern Recognition
Problem Type: Generate All Subsets (Power Set)
Core Pattern: Backtracking with Skip/Take Decision
When to Apply:
✓ Generate all possible subsets
✓ All combinations of any size
✓ Power set generation
✓ No duplicates in input
Recognition Keywords:
- "all possible subsets"
- "power set"
- "all combinations"
- "unique elements"
Key Components:
┌────────────────────────────────────────────┐
│ Binary Decision: SKIP or TAKE each element│
│ Step 1: SKIP → recurse(index + 1) │
│ Step 2: TAKE → add → recurse → remove │
│ Step 3: BACKTRACK → remove last │
│ Base case: index == nums.length │
│ Time: O(n × 2^n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is subsets - binary skip/take decision"
Step 2: "At each index, first SKIP then TAKE element"
Step 3: "Add result at base case when index reaches end"
Key Points to Mention:
- Each element: binary decision (skip or take)
- Total subsets: 2^n
- Clean pattern: Skip first, Take second, Backtrack
- Add to result only at base case
- Order: subsets without element, then with element
Walk Through Example:
"For nums=[1,2,3]:
At index 0 (element 1):
First SKIP 1:
At index 1, SKIP 2:
At index 2, SKIP 3 → Add [] ✓
At index 2, TAKE 3 → Add [3] ✓
At index 1, TAKE 2:
SKIP 3 → Add [2] ✓
TAKE 3 → Add [2,3] ✓
Then TAKE 1:
At index 1, SKIP 2:
SKIP 3 → Add [1] ✓
TAKE 3 → Add [1,3] ✓
At index 1, TAKE 2:
SKIP 3 → Add [1,2] ✓
TAKE 3 → Add [1,2,3] ✓
Total: 8 subsets"
Why This Order:
"SKIP first generates all subsets WITHOUT element
TAKE second generates all subsets WITH element
Clean separation!"
Complexity:
"Time: O(n × 2^n)
- Generate 2^n subsets
- Each takes O(n) to copy
Space: O(n) for recursion depth"
📝 Quick Revision Notes
🎯 Core Concept:
Subsets (Power Set): Generate all possible subsets. Each element has binary decision (SKIP or TAKE). Use backtracking with 3-step pattern: (1) SKIP → recurse, (2) TAKE → add → recurse, (3) BACKTRACK → remove. Add to result at base case (index == length). Total: 2^n subsets.
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public List<List<Integer>> subsets(int[] a) {
// return recursive(a);
// return iterative(a);
return binary(a);
}
private List<List<Integer>> binary(int[] a) {
// Approach: input [1,2,3]
// Number of items in output: 2^3 = 8
// Consider having from 000, 001, ... 111
// If its 000, no element from array: {} => add empty list to res
// If its 001, add a[0] only => {3}
// If its 011, add a[1] and a[0] only => {2,3} and so on
// which all subsets come.
List<List<Integer>> res = new ArrayList<>();
// step 1: number of results.
int count = 1 << a.length;
// step 2: now loop from 0 to count
for (int i = 0; i < count; i++) {
List<Integer> curr = new ArrayList<>();
// step 3: check if jth bit is set in a 32-bit number
for (int j = 0; j < 32; j++) {
// For example i = 5 (101)
// j=0 => 1 << 0 => 001 << 0 => 001 and now 001 & 101 => 0th bit is set
// j=1 => 1 << 1 => 001 << 1 => 010 and now 010 & 101 => 1st bit is not set
// j=2 => 1 << 2 => 001 << 2 => 100 and now 100 & 101 => 2nd bit is set
// Based upon bit is set or not, add it to result
if (((1 << j) & i) != 0) {
curr.add(a[j]);
}
}
// step 4: add curr list to res list
res.add(new ArrayList<>(curr));
}
return res;
}
private List<List<Integer>> iterative(int[] a) {
// Approach: input [1,2,3]
// Initial: put empty list {} in queue
// One diff with prev problems is we do not poll any
// elements from queue
// Take 1:
// Add 1 to all lists in queue (which currently has {})
// resultant queue: {}, {1}
// Take 2:
// Add 2 to all lists in queue (which currently has {},{1})
// resultant queue: {}, {1}, {2}, {1,2}
// Take 3:
// Add 3 to all lists in queue (which currently has {},{1},{2},{1,2})
// resultant queue: {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}
List<List<Integer>> res = new ArrayList<>();
Queue<List<Integer>> queue = new LinkedList<>();
queue.offer(new ArrayList<>());
for (int i = 0; i < a.length; i++) {
int size = queue.size();
for (int j = 0; j < size; j++) {
// GOTCHA:
// why polled when we need to have?
// If we cannot poll, we cannot get next elements.
// So, poll it and again push it.
List<Integer> curr = queue.poll();
queue.offer(new ArrayList<>(curr));
curr.add(a[i]);
queue.offer(new ArrayList<>(curr));
}
}
res.addAll(queue);
return res;
}
private List<List<Integer>> recursive(int[] a) {
// Approach:
// Consider [1,2,3]
// Start with 1st element at index 0 which is 1.
// With that element, we can do 2 things: take it or skip it
// Add both scenarios to the curr list and continue to the next element.
// Once we complete considering all elements (either take or skip) and
// when index == a.length, add to result.
List<List<Integer>> res = new ArrayList<>();
recursiveUtil(a, 0, new ArrayList<>(), res);
return res;
}
private void recursiveUtil(int[] a, int index, ArrayList<Integer> curr, List<List<Integer>> res) {
// step 4: base case
if (index == a.length) {
res.add(new ArrayList<>(curr));
return;
}
// step 1: skip the element at current index and proceed
// to next element (index is currIndex + 1)
recursiveUtil(a, index + 1, curr, res);
// step 2: take the element at current index and proceed
// to next element (index is currIndex + 1)
curr.add(a[index]);
recursiveUtil(a, index + 1, curr, res);
// step 3: backtrack - remove the added element to get
// back to the previous state
curr.remove(curr.size() - 1);
}
public static void main(String[] args) {
Solution s = new Solution();
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
System.out.println(s.subsets(new int[] { 1, 2, 3 }));
// [[],[0]]
System.out.println(s.subsets(new int[] { 0 }));
}
}
🔑 Key Insights:
- Pattern: Skip/Take Binary Decision
- 3 Steps: (1) SKIP, (2) TAKE + recurse, (3) BACKTRACK
- Order Matters: SKIP first, TAKE second
- Add at Base Case: When index == nums.length
- Clean Separation: Without element first, with element after
- Time: O(n × 2^n), Space: O(n) ✓
🎪 Memory Aid:
"Skip first, take second, backtrack third!"
"Add at end, 2^n total!" ✨
⚠️ The 3-Step Pattern:
At each index i:
┌──────────────────────────────────────────┐
│ Step 1: SKIP │
│ backtrack(index + 1) │
│ Don't modify curr │
│ Generates subsets WITHOUT this element│
├──────────────────────────────────────────┤
│ Step 2: TAKE │
│ curr.add(nums[index]) │
│ backtrack(index + 1) │
│ Generates subsets WITH this element │
├──────────────────────────────────────────┤
│ Step 3: BACKTRACK │
│ curr.remove(curr.size() - 1) │
│ Restore state for other branches │
└──────────────────────────────────────────┘
Without step 3:
curr = [1,2,3] forever! ✗
With step 3:
curr properly restored for other paths ✓
🧪 Edge Cases
Case 1: Single element
Input: nums = [1]
Output: [[], [1]]
2^1 = 2 subsets
Case 2: Two elements
Input: nums = [1,2]
Output: [[], [2], [1], [1,2]]
2^2 = 4 subsets
Case 3: Three elements
Input: nums = [1,2,3]
Output: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
2^3 = 8 subsets
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(n × 2^n)
Why 2^n subsets?
Each element: 2 choices (skip or take)
Total: 2 × 2 × 2 × ... (n times) = 2^n
Why × n?
Each subset takes O(n) to copy to result
Total: 2^n × n
Example:
n=3: 2³ = 8 subsets, 8 × 3 = 24 operations
n=4: 2⁴ = 16 subsets, 16 × 4 = 64 operations
n=10: 2¹⁰ = 1024 subsets, 1024 × 10 = 10,240 operations
Space Complexity: O(n)
Recursion stack:
Maximum depth = n
(One level for each element)
Current list: O(n) worst case
Total: O(n) auxiliary space
Output space: O(n × 2^n) - not counted
📚 Related Problems
Same Core Pattern: - Subsets II (LC 90) - With duplicate elements - Combinations (LC 77) - Fixed size k - Combination Sum (LC 39) - Sum to target
Similar Binary Decision: - Letter Case Permutation (LC 784) - Uppercase/lowercase - Partition Equal Subset Sum (LC 416) - DP with subsets
Happy practicing! 🎯
Note: This skip/take pattern is more intuitive than the loop approach! It makes the binary decision crystal clear: at each element, you either SKIP it or TAKE it. This pattern appears in many problems - even in DP (0/1 knapsack)! Master this and you'll recognize it everywhere! 💪✨