101 — Subsets

101 — Subsets

LeetCode 78 · Medium. 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 answer in any order.

---

🍽️ Intuition

Every element in nums has exactly two possible fates in any given subset: it's either in, or it's out. That binary choice, repeated independently for each of the n elements, is exactly the "include / exclude" branching from chapter 18 — and Subsets is the purest possible expression of it, because unlike almost every other problem in this batch, there's no validity constraint to check along the way. Every partial choice you make is already a complete, legal answer — you don't need to reach the end of the array to have built something worth recording.

---

🚩 Pattern-Recognition Cue

"Return all possible subsets" (or "the power set") is about as direct a backtracking cue as they come — "all possible X" is the tell from chapter 18's recognition signal, and "subset" specifically means every node visited during the search, not just the leaves, is itself a valid answer worth recording.

---

🐢 Brute Force

Enumerate every integer bitmask from 0 to 2^n - 1; each mask's binary representation says, bit by bit, which elements belong in that subset. Decoding a mask means scanning all n bits, every time, regardless of how many are actually set.

func subsetsBruteForce(_ nums: [Int]) -> [[Int]] {
    let n = nums.count
    var results: [[Int]] = []

    for mask in 0..<(1 << n) {
        var subset: [Int] = []
        for i in 0..<n {
            if mask & (1 << i) != 0 {
                subset.append(nums[i])
            }
        }
        results.append(subset)
    }

    return results
}

// smoke test
print(subsetsBruteForce([1, 2, 3]).count)   // 8
print(subsetsBruteForce([]))                 // [[]]
print(subsetsBruteForce([5]))                // [[], [5]]

Big-O: O(n · 2^n) time — 2^n masks, each requiring an O(n) bit scan to decode. O(n) extra space per subset being built, not counting the output itself.

---

🚀 Optimal

Build subsets incrementally with a single shared path array, recording it on every recursive call (every node is a valid subset) and only ever extending it by one element at a time before undoing that choice.

func subsets(_ nums: [Int]) -> [[Int]] {
    var results: [[Int]] = []
    var path: [Int] = []

    func backtrack(_ start: Int) {
        results.append(path)   // every node is a valid subset — record unconditionally

        for i in start..<nums.count {
            path.append(nums[i])
            backtrack(i + 1)
            path.removeLast()
        }
    }

    backtrack(0)
    return results
}

// smoke test — same cases as the brute force
print(subsets([1, 2, 3]).count)   // 8
print(subsets([]))                 // [[]]
print(subsets([5]))                // [[], [5]]

Big-O: O(n · 2^n) time — same total output size, but each recursive call does O(1) work beyond the O(k) copy made when recording a subset of size k. O(n) extra space for the recursion stack and path, not counting the output.

---

🔑 The Key Insight

Subsets is the one problem in this batch where there's no invalid branch to prune — every node in the recursion tree, at every depth, is already a legitimate subset. So the brute-force-vs-optimal gap here isn't about skipping dead branches (there aren't any); it's about how much wasted work happens on the way to each answer. Decoding a bitmask re-scans all n bits for every one of the 2^n masks, whether that particular subset needs 0 or n elements. Backtracking's shared path array only ever does work proportional to what's actually changing at each step — append one element, recurse, remove one element — so the total work tracks the real shape of the output instead of a fixed n-wide scan repeated 2^n times.

---

🔗 Related Chapters

• DFS and Backtracking — this chapter's generic template, used almost verbatim: the "record unconditionally" variant, since every subset is valid.
• Arrays and Strings — path is mutated in place with append/removeLast throughout the search; Swift's copy-on-write array semantics are why that's cheap.

---

🧸 Memory Sentence

Subsets is the "include or exclude every element" tree walked all the way through — and because every node is already a valid answer, you record on the way down, not just at the leaves.

---

✅ Check Your Understanding

1. Why does subsets call results.append(path) unconditionally at the top of backtrack, instead of guarding it behind a completion check the way some other problems in this chapter do?
2. nums = [] should produce [[]] — one subset, the empty one — not []. Trace through subsets([]) and identify which line produces that empty-subset record.
3. Both the brute-force bitmask version and the optimal backtracking version are O(n · 2^n) in the worst case. Where, concretely, does backtracking still save real work if the asymptotic bound is the same?

---

⬅️ Previous: Find Median from Data Stream · Next: Combination Sum ➡️