LeetCode · #78

Subsets Solution

Given an integer array of unique elements, return all possible subsets (the power set) without duplicates in any order.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #78

🏗️

Pattern

Backtracking — include/exclude

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets and may be returned in any order.

Example

 Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
// 2³ = 8 subsets total (including empty set) 

Constraints

 • 1 ≤ nums.length ≤ 10  ← at most 2¹⁰ = 1024 subsets — bitmask is feasible • -10 ≤ nums[i] ≤ 10 • All numbers in nums are unique 

Section Two · Approach 1

Bitmask — O(n·2ⁿ)

For n elements there are 2ⁿ subsets. Represent each subset as an integer from 0 to 2ⁿ−1. Bit i being set means nums[i] is included. Iterate all integers and decode which bits are set.

Why it works

Each number from 0 to 2ⁿ−1 is a unique binary pattern that perfectly encodes one possible include/exclude decision per element. No subset is generated twice and none is missed.

Why we can do better

Problem: Bitmask is hard to extend when duplicates exist (LC 90) or when you need additional constraints (e.g. size = k). Backtracking builds subsets incrementally, making it easy to prune and generalize to combination/partition problems.

Java — Bitmask

 import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) subset.add(nums[i]);
            }
            res.add(subset);
        }
return res;
    }
}

Python — Bitmask

 class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
        n, res = len(nums), []
for mask in range(1 << n):
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            res.append(subset)
return res

Metric	Value
Time	O(n · 2ⁿ) — 2ⁿ masks × n bits each
Space	O(n · 2ⁿ) — output storage

Section Three · Approach 2

Backtracking — O(n·2ⁿ)

At each position in the array, make a binary decision: include or exclude the current element. Recurse into both branches, then undo the choice. Every leaf of the decision tree is a valid subset.

💡 Mental model: Think of packing a bag for a trip. You stand in front of your wardrobe and for each item decide "take it or leave it." You go through every item in order. After deciding, you come back, remove the last item you included, and try the "leave it" path. By the time you've walked every path through the wardrobe, you've considered every packing combination.

Algorithm — Backtracking (DFS)

State: current index i and current subset path.
Base case: when i == nums.length, add a copy of path to the result.
Include: push nums[i], recurse with i+1.
Exclude: pop nums[i], recurse with i+1 (backtrack).
No need to sort — all elements are unique, order doesn't matter for correctness.

🎯 When to recognize this pattern:

The signal is "generate all possible combinations / subsets / partitions." You see the word "all" and the output is a list of lists.
This exact template (index + path + choose/unchoose) solves LC 90 (Subsets II), LC 39 (Combination Sum), and LC 131 (Palindrome Partitioning) with minor modifications.

Why copying path matters:

path is a mutable list shared across all recursive calls.
If you add the reference directly to the result, every entry in the result will point to the same (eventually empty) list.
Always add new ArrayList<>(path) in Java or path[:] in Python.

Section Four · Trace

Visual Walkthrough

Trace for nums = [1, 2, 3]. The decision tree expands left (include) then right (exclude) at each level.

Backtracking Decision Tree — nums = [1, 2, 3]

Section Five · Implementation

Code — Java & Python

Java — Backtracking

 import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
    }
private void backtrack(int[] nums, int i,
List<Integer> path,
List<List<Integer>> res) {
if (i == nums.length) {
            res.add(new ArrayList<>(path)); // copy — path is mutable return;
        }
// Include nums[i]
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
// Exclude nums[i] (backtrack)
path.remove(path.size() - 1);
backtrack(nums, i + 1, path, res);
    }
}

Python — Backtracking

 class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
        res, path = [], []
def backtrack(i: int) -> None:
if i == len(nums):
                res.append(path[:]) # snapshot — path is mutable return
path.append(nums[i]) # include backtrack(i + 1)
            path.pop() # exclude (backtrack) backtrack(i + 1)
backtrack(0)
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Cascading (iterative)	O(n · 2ⁿ)	O(n · 2ⁿ)	Simple loop but hard to prune for constrained variants
Bitmask	O(n · 2ⁿ)	O(n · 2ⁿ)	Elegant but only works when n ≤ 32
Backtracking ← optimal	O(n · 2ⁿ)	O(n) recursion + O(n · 2ⁿ) output	Generalizes to duplicates, constraints; O(n) call stack

Why not just use an iterative cascading approach?:

Cascading works well for subsets but breaks when you add constraints like "no duplicates" (LC 90) or "must sum to target" (LC 39).
Backtracking naturally prunes invalid paths before they're fully built, avoiding wasted work at each recursive step.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[5]`	Two subsets: `[]` and `[5]`. Base case fires immediately on both branches.
Empty output row	any input	The empty set `[]` is always a valid subset — generated when all elements are excluded.
Negative numbers	`[-1, 0, 1]`	Algorithm is comparison-free; negatives work without special handling.
All zeros	`[0, 0, 0]`	Not possible per constraints (all elements unique), but illustrates why uniqueness matters.
Max input n=10	10 elements	2¹⁰ = 1024 subsets. Well within memory. Stack depth = 10.
Shallow copy missing	any	Forgetting `new ArrayList<>(path)` causes all result entries to be the same empty list at the end.

⚠ Common Mistake: Writing res.add(path) instead of res.add(new ArrayList<>(path)). Since path is reused across all recursive calls, every entry in res will reference the same list object. By the time recursion finishes, every "subset" will look like the final empty path. Always snapshot with a copy.

← Back to Backtracking problems

LearningTree

LC 78 · Subsets — Solution & Explanation | DSA Guide