Subsets — The Packing List

Welcome to Dungeon 9

Every dungeon so far asked for an answer: a number, a node, a yes/no. This dungeon asks for all of them: every subset, every ordering, every arrangement that satisfies the rules. The output isn't a value, it's a catalog.

The method has one name, backtracking, and one rhythm, met briefly in the Tries dungeon and now promoted to the whole show:

Choose. Explore. Un-choose.

Make a decision, recurse into the world where that decision holds, then undo it, restoring the world exactly, and make the next decision. The call stack becomes a time machine: every return is a step backward into a past where you hadn't chosen yet.

Boss 1 is the rhythm in its purest form. No constraints, no pruning, no traps. Just every possibility, generated cleanly.

The story

Weekend trip, three items on the bed: camera, umbrella, snacks (call them 1, 2, 3). You can't decide what to pack, so, in a fit of engineering, you decide to enumerate every possible packing and pick later.

The empty bag counts (minimalism). The everything-bag counts. All told, with three items:

[]  [1]  [2]  [3]  [1,2]  [1,3]  [2,3]  [1,2,3]

Eight bags. And eight is no accident: each item is one independent yes/no decision, three decisions, 2 × 2 × 2 = 2³ = 8. Every subset problem starts with this arithmetic, n items, 2ⁿ subsets, so nobody expects better than exponential output. The craft is generating them without duplicates, without omissions, and without chaos.

The clean procedure: consider the items in a fixed order, and for each one, branch twice.

camera?  ── yes ──  umbrella? ── yes ── snacks? ...
         └─ no ──   umbrella? ── ...

At the bottom of every branch-path lies one complete decision sheet: one subset. Eight leaves, eight bags. Walk the tree with one real bag in hand: at a "yes", put the item in; explore everything below; then take it out and explore the "no" side. One bag, reused for all eight outcomes, that's the memory frugality that makes backtracking scale as well as anything exponential can.

The problem, dressed up properly

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.

LeetCode 78. "Unique elements" is load-bearing, Boss 4 removes it and charges admission.

The naive attempt

Nested loops? Three loops enumerate three-item subsets only; you'd need a loop per item, and n isn't known at write time. The genuinely useful naive version is the bitmask: every number from 0 to 2ⁿ-1 is a subset, bit i says whether item i goes in.

def subsets(nums):
    n = len(nums)
    out = []
    for mask in range(1 << n):
        out.append([nums[i] for i in range(n) if mask & (1 << i)])
    return out

This is correct, compact, and worth knowing (Dungeon 17 will wink at it). What it doesn't give you is a skeleton that survives contact with constraints: add "no two adjacent items" or "sum must equal k" and the bitmask version filters after generating, while the recursive version prunes while generating. The whole dungeon runs on that difference, so the recursion is the version to internalize.

The weapon: choose, explore, un-choose

One shared list path (the real bag), one recursion over item indices:

def subsets(nums: list[int]) -> list[list[int]]:
    out = []
    path = []
 
    def decide(i):
        if i == len(nums):
            out.append(path[:])      # copy! the bag itself keeps changing
            return
        path.append(nums[i])         # choose: item goes in
        decide(i + 1)                # explore that world
        path.pop()                   # un-choose: exactly restore
        decide(i + 1)                # explore the other world
    decide(0)
    return out

Three lines are the entire pattern, and each earns a name worth keeping:

• path.append / path.pop, symmetric. Every choose has exactly one un-choose, same depth, same item. Between them, anything may happen; around them, the bag is untouched. This symmetry is backtracking; every bug in this dungeon is a broken symmetry.
• path[:] at the leaf. The single most classic mistake in all of backtracking is out.append(path), storing a reference to the shared bag. The recursion keeps mutating it, and you end up with eight copies of the same (finally empty!) list. Snapshot at the moment of completion. Tattoo path[:] somewhere.
• The index i. Decisions in fixed order, no revisiting. That's what guarantees no duplicates and no omissions: each subset corresponds to exactly one root-to-leaf path.

Watching it work

nums = [1, 2, 3], following the bag:

decide(0) choose 1
  decide(1) choose 2
    decide(2) choose 3 → leaf [1,2,3]  pop 3
    decide(2) skip 3   → leaf [1,2]
  pop 2
  decide(1) skip 2
    decide(2) choose 3 → leaf [1,3]   pop 3
    decide(2) skip 3   → leaf [1]
pop 1
decide(0) skip 1
  ... → [2,3], [2], [3], []

Eight leaves, each visited once, and the bag ends exactly as it began: empty. If your path isn't empty when the recursion finishes, a pop went missing, that's the standard smoke test.

Gotchas

1. Appending the live list. out.append(path) , the reference bug described above. Symptom: all results identical (usually all empty). Cure: path[:] or list(path).

2. Asymmetric choose/un-choose. A pop inside an if, or an early return between append and pop, leaves phantom items in the bag for every later branch. Symmetry is structural: append and pop at the same indentation, nothing escaping between them.

3. Re-deciding decided items. Recursing with i instead of i + 1 (or looping from 0 instead of i) revisits items, producing [1,1] bags and infinite trees. The index only moves forward.

4. Expecting a polynomial algorithm. 2ⁿ subsets exist; any correct algorithm outputs 2ⁿ things. When an interviewer asks the complexity, the answer O(n · 2ⁿ) isn't an apology, it's the size of the answer itself. Say it with a straight face.

Complexity

2ⁿ leaves, each copied in O(n).

Time: O(n · 2ⁿ). Space: O(n) for the path and stack, output aside.

Boss down. XP gained.

Eight bags laid out on the bed. You pick [camera, snacks], obviously, and the umbrella stays home. It doesn't rain. Enumeration wins again.

What you walked away with:

• The rhythm: choose, explore, un-choose, with surgical symmetry
• One shared path, many results, copy at the moment of completion
• Fixed decision order = each result generated exactly once
• 2ⁿ is the output's size; exponential is the job, not a failure
• Two skeletons (branch-per-decision, loop-over-candidates), one soul

Boss 1 had no rules, every leaf counted. The next boss adds a target and a twist: items may be reused, and branches that overshoot get cut mid-air, your first taste of pruning, the thing that separates backtracking from brute force.

Next up: Boss 2 — The Balance Weights. An old market scale, brass weights of a few sizes with unlimited copies of each, and a target pan to balance exactly. Combinations that repeat, a sum that must land precisely, and the sorted-input trick that lets a whole subtree die the moment the pan tips over.