Leetcode 78 : Subsets

Recursion · Backtracking · The call stack

Subsets on the Stack

Every subset of a set is one path through a tree of yes/no decisions. Watch the machine walk that tree — pushing a frame each time it goes deeper, popping one each time it comes back.

Input set { 1, 2, 3 } → expect 2³ = 8 subsets

The machine

Step through it

The tree shows where you are. The stack shows how you got there — one frame per unfinished call, each one paused mid-line, waiting for the call above it to finish.

start Press Play, or step with the arrow keys.

Code · current line

1void findSubsets(int index) {2    if (index == nums.length) {3        results.add(new ArrayList<>(current));4        return;5    }6    current.add(nums[index]);          // TAKE7    findSubsets(index + 1);            // explore8    current.remove(current.size()-1);  // UN-TAKE9    findSubsets(index + 1);            // SKIP10}

Call stack

current (the shared bag)

empty

results

0 / 8 recorded

step 0 / 0

Keyboard: ← and → step, space plays and pauses.

The thing that confuses everyone

Two kinds of memory, only one of which cleans itself up

Every frame on that stack carries its own copy of index. Java saves and restores it for you — that is what a stack frame is. But there is only one current list in the entire program, shared by every frame. Nobody restores it for you.

index — per frame, automatic

frame 4index = 3

frame 3index = 2

frame 2index = 1

frame 1index = 0

Four live frames, four separate index values, each sealed inside its own frame. When a frame pops, its index vanishes with it and the caller finds its own value exactly as it left it.

You never write code to restore index. The hardware stack does it.

current — one object, shared

↓  ↓  ↓  ↓

current = [ 1, 2, 3 ]

all four frames point here

Every frame holds a reference to the same ArrayList. A frame that adds to it has changed the world for its caller too — the change outlives the frame that made it.

So the caller must undo it by hand. That is the whole job of line 8: current.remove(...) is the manual restore for the one piece of state the stack won't restore for you.

The stack restores what belongs to a frame. You restore what everyone shares.

Reading the picture

Five things the animation is showing you

• Going down = pushing. Line 7 and line 9 are the only two places the stack grows. Each one is a question: “what happens if I take it?” and “what happens if I don't?”
• The paused frames are the path. The frames below the top aren't idle — each is frozen mid-line, holding the return point. Read the stack bottom-to-top and you read the highlighted path down the tree.
• Recording happens only at leaves. A subset is complete only when there are no decisions left. That's index == nums.length — the base case, the only place anything is written to results.
• Backtracking happens on the way up. Line 8 runs after a whole branch has finished and returned. That's why it doesn't look like it belongs where it sits in the code.
• The tree is never built. There's no tree object in memory — only the current root-to-node path, alive as stack frames. Everything to the left has been popped; everything to the right doesn't exist yet.

The cost

Why the stack stays small even though the answer is huge

The tree has 15 nodes and 8 leaves, but at no moment do more than 4 frames exist. The machine walks the tree depth-first, so it only ever holds one root-to-leaf path — which is why recursion depth is n + 1, not 2ⁿ.

Quantity	For n = 3	In general
Subsets produced	8	2ⁿ
Nodes in the tree	15	2ⁿ⁺¹ − 1
Max frames alive at once	4	n + 1
Time	~24 ops	O(n · 2ⁿ)
Stack space	4 frames	O(n)

Total steps in this trace: —. Every one of them is a push, a pop, an add, a remove, or a record. There is nothing else in backtracking.

Choose. Explore. Un-choose. The stack handles the rest.