w-22-backtracking-tree.yml · YAML
YAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAML
# Backtracking decision tree
# Three-way-shared widget across Part 7 (chapters 7.1, 7.2). Chapter 7.2 owns
# three panels (subsets / permutations / combination sum) animating the
# decision tree expansion under the choose-explore-unchoose chassis.
# Chapter 7.1 owns one scaffold panel for the generic template trace; the
# 7.1 author fills the keyframes when the chapter ships.
id: w-22-backtracking-tree
title: "Backtracking decision tree"
type: three-way-shared
level: 1
modes: [preset, edit]
caps:
array_length: { min: 1, max: 6 }
# Hard cap n=6 keeps subsets at 64 nodes, permutations at 720 leaves; both
# well under the 30-step animation ceiling at the canonical n=3 input.
commands:
- name: pushChoice
payload: { value: 'integer | string', depth: 'integer' }
description: "Take a choice at the current depth. Highlight the new path edge; activate the new child node."
- name: snapshot
payload: { path: 'array' }
description: "Snapshot the current path into the result list (subsets: every node; permutations: leaves only; combination sum: when target hit)."
- name: prune
payload: { reason: 'string' }
description: "Branch-and-bound cut. Mark the rejected subtree; do not recurse."
- name: popChoice
payload: { value: 'integer | string' }
description: "Undo the most recent choice. Highlight returns to the parent; child subtree fades."
- name: done
payload: { count: 'integer' }
description: "Recursion complete. Display total snapshots collected."
static_fallback:
generator: jsdom
output: site/static/widgets/w-22-backtracking-tree-fallback.svg
keyframes_used: [0, "n_steps/4", "n_steps/2", "n_steps-1"]
panels:
panel-subsets:
chapter: "7.2"
label: "Subsets decision tree (LC 78)"
canonical_input: |
nums = [1, 2, 3]
presets:
- id: canonical
label: "Canonical [1, 2, 3]"
input: { nums: [1, 2, 3] }
- id: with_zero
label: "Single element [0]"
input: { nums: [0] }
- id: pair
label: "Pair [1, 2]"
input: { nums: [1, 2] }
n_steps: 23
# Trace generated by running the verified §2.2 Python reference with
# instrumentation; deterministic re-run produces identical
# output.
keyframes:
- step: 0
kind: snapshot
payload: { path: [] }
state: { stack_depth: 0, path: [], emitted: 1, current_node: "root" }
narration: "Snapshot at root. Emit subset 1: []."
- step: 1
kind: pushChoice
payload: { value: 1, depth: 0 }
state: { stack_depth: 1, path: [1], emitted: 1, current_node: "[1]" }
narration: "Choose 1 at depth 0. Path = [1]."
- step: 2
kind: snapshot
payload: { path: [1] }
state: { stack_depth: 1, path: [1], emitted: 2, current_node: "[1]" }
narration: "Snapshot. Emit subset 2: [1]."
- step: 3
kind: pushChoice
payload: { value: 2, depth: 1 }
state: { stack_depth: 2, path: [1, 2], emitted: 2, current_node: "[1,2]" }
narration: "Choose 2 at depth 1. Path = [1, 2]."
- step: 4
kind: snapshot
payload: { path: [1, 2] }
state: { stack_depth: 2, path: [1, 2], emitted: 3, current_node: "[1,2]" }
narration: "Snapshot. Emit subset 3: [1, 2]."
- step: 5
kind: pushChoice
payload: { value: 3, depth: 2 }
state: { stack_depth: 3, path: [1, 2, 3], emitted: 3, current_node: "[1,2,3]" }
narration: "Choose 3 at depth 2. Path = [1, 2, 3]."
- step: 6
kind: snapshot
payload: { path: [1, 2, 3] }
state: { stack_depth: 3, path: [1, 2, 3], emitted: 4, current_node: "[1,2,3]" }
narration: "Snapshot. Emit subset 4: [1, 2, 3]. Loop exhausted; backtrack."
- step: 7
kind: popChoice
payload: { value: 3 }
state: { stack_depth: 2, path: [1, 2], emitted: 4, current_node: "[1,2]" }
narration: "Pop 3. Path = [1, 2]. Loop exhausted at depth 1; backtrack."
- step: 8
kind: popChoice
payload: { value: 2 }
state: { stack_depth: 1, path: [1], emitted: 4, current_node: "[1]" }
narration: "Pop 2. Path = [1]. Continue loop at depth 0 from i=2."
- step: 9
kind: pushChoice
payload: { value: 3, depth: 1 }
state: { stack_depth: 2, path: [1, 3], emitted: 4, current_node: "[1,3]" }
narration: "Choose 3 at depth 1 (skipping 2 via start index). Path = [1, 3]."
- step: 10
kind: snapshot
payload: { path: [1, 3] }
state: { stack_depth: 2, path: [1, 3], emitted: 5, current_node: "[1,3]" }
narration: "Snapshot. Emit subset 5: [1, 3]. Loop exhausted; backtrack."
- step: 11
kind: popChoice
payload: { value: 3 }
state: { stack_depth: 1, path: [1], emitted: 5, current_node: "[1]" }
narration: "Pop 3. Path = [1]. Loop exhausted at depth 0; backtrack."
- step: 12
kind: popChoice
payload: { value: 1 }
state: { stack_depth: 0, path: [], emitted: 5, current_node: "root" }
narration: "Pop 1. Path = []. Continue loop at root from i=1."
- step: 13
kind: pushChoice
payload: { value: 2, depth: 0 }
state: { stack_depth: 1, path: [2], emitted: 5, current_node: "[2]" }
narration: "Choose 2 at depth 0 (skipping 1 via start index). Path = [2]."
- step: 14
kind: snapshot
payload: { path: [2] }
state: { stack_depth: 1, path: [2], emitted: 6, current_node: "[2]" }
narration: "Snapshot. Emit subset 6: [2]."
- step: 15
kind: pushChoice
payload: { value: 3, depth: 1 }
state: { stack_depth: 2, path: [2, 3], emitted: 6, current_node: "[2,3]" }
narration: "Choose 3 at depth 1. Path = [2, 3]."
- step: 16
kind: snapshot
payload: { path: [2, 3] }
state: { stack_depth: 2, path: [2, 3], emitted: 7, current_node: "[2,3]" }
narration: "Snapshot. Emit subset 7: [2, 3]. Loop exhausted; backtrack."
- step: 17
kind: popChoice
payload: { value: 3 }
state: { stack_depth: 1, path: [2], emitted: 7, current_node: "[2]" }
narration: "Pop 3. Path = [2]. Loop exhausted at depth 1; backtrack."
- step: 18
kind: popChoice
payload: { value: 2 }
state: { stack_depth: 0, path: [], emitted: 7, current_node: "root" }
narration: "Pop 2. Path = []. Continue loop at root from i=2."
- step: 19
kind: pushChoice
payload: { value: 3, depth: 0 }
state: { stack_depth: 1, path: [3], emitted: 7, current_node: "[3]" }
narration: "Choose 3 at depth 0. Path = [3]."
- step: 20
kind: snapshot
payload: { path: [3] }
state: { stack_depth: 1, path: [3], emitted: 8, current_node: "[3]" }
narration: "Snapshot. Emit subset 8: [3]. Loop exhausted; backtrack."
- step: 21
kind: popChoice
payload: { value: 3 }
state: { stack_depth: 0, path: [], emitted: 8, current_node: "root" }
narration: "Pop 3. Path = []. Loop exhausted at root; recursion complete."
- step: 22
kind: done
payload: { count: 8 }
state: { stack_depth: 0, path: [], emitted: 8, current_node: null }
narration: "Done. 2^3 = 8 subsets collected; bijection with the decision tree's nodes."
panel-perms:
chapter: "7.2"
label: "Permutations decision tree (LC 46)"
canonical_input: |
nums = [1, 2, 3]
presets:
- id: canonical
label: "Canonical [1, 2, 3]"
input: { nums: [1, 2, 3] }
n_steps: 24
# Trace expanded by hand-tracing the §2.1 permutations pseudocode against
# nums=[1,2,3]; produces 3! = 6 permutations in lexicographic DFS order.
# The used[] mask is rendered as a row of three boolean cells beside the
# tree; activations and clearings drive the visual.
keyframes:
- step: 0
kind: init
state: { used: [false, false, false], path: [], emitted: 0, current_node: "root" }
narration: "About to enumerate permutations of [1, 2, 3]. used[] all false; path empty."
- step: 1
kind: pushChoice
payload: { value: 1, depth: 0 }
state: { used: [true, false, false], path: [1], emitted: 0, current_node: "[1]" }
narration: "Choose 1 at depth 0. used[0] = true; path = [1]."
- step: 2
kind: pushChoice
payload: { value: 2, depth: 1 }
state: { used: [true, true, false], path: [1, 2], emitted: 0, current_node: "[1,2]" }
narration: "Choose 2 at depth 1. used[1] = true; path = [1, 2]."
- step: 3
kind: pushChoice
payload: { value: 3, depth: 2 }
state: { used: [true, true, true], path: [1, 2, 3], emitted: 0, current_node: "[1,2,3]" }
narration: "Choose 3 at depth 2. used[2] = true; path = [1, 2, 3]. Length matches n; snapshot at leaf."
- step: 4
kind: snapshot
payload: { path: [1, 2, 3] }
state: { used: [true, true, true], path: [1, 2, 3], emitted: 1, current_node: "[1,2,3]" }
narration: "Emit permutation 1: [1, 2, 3]. Backtrack."
- step: 5
kind: popChoice
payload: { value: 3 }
state: { used: [true, true, false], path: [1, 2], emitted: 1, current_node: "[1,2]" }
narration: "Pop 3. used[2] = false; loop exhausted at depth 1; backtrack again."
- step: 6
kind: popChoice
payload: { value: 2 }
state: { used: [true, false, false], path: [1], emitted: 1, current_node: "[1]" }
narration: "Pop 2. used[1] = false; continue loop at depth 1 from i=2."
- step: 7
kind: pushChoice
payload: { value: 3, depth: 1 }
state: { used: [true, false, true], path: [1, 3], emitted: 1, current_node: "[1,3]" }
narration: "Choose 3 at depth 1 (skipping i=0 because used[0]). used[2] = true; path = [1, 3]."
- step: 8
kind: pushChoice
payload: { value: 2, depth: 2 }
state: { used: [true, true, true], path: [1, 3, 2], emitted: 1, current_node: "[1,3,2]" }
narration: "Choose 2 at depth 2. Path = [1, 3, 2]. Length matches n."
- step: 9
kind: snapshot
payload: { path: [1, 3, 2] }
state: { used: [true, true, true], path: [1, 3, 2], emitted: 2, current_node: "[1,3,2]" }
narration: "Emit permutation 2: [1, 3, 2]. Backtrack two levels."
- step: 10
kind: popChoice
payload: { value: 2 }
state: { used: [true, false, true], path: [1, 3], emitted: 2, current_node: "[1,3]" }
narration: "Pop 2. used[1] = false; loop exhausted at depth 1; backtrack again."
- step: 11
kind: popChoice
payload: { value: 3 }
state: { used: [true, false, false], path: [1], emitted: 2, current_node: "[1]" }
narration: "Pop 3. used[2] = false; loop exhausted at depth 0; backtrack to root subtree under 1."
- step: 12
kind: popChoice
payload: { value: 1 }
state: { used: [false, false, false], path: [], emitted: 2, current_node: "root" }
narration: "Pop 1. used[0] = false; continue loop at root from i=1."
- step: 13
kind: pushChoice
payload: { value: 2, depth: 0 }
state: { used: [false, true, false], path: [2], emitted: 2, current_node: "[2]" }
narration: "Choose 2 at depth 0. Subtree under 2 begins."
- step: 14
kind: pushChoice
payload: { value: 1, depth: 1 }
state: { used: [true, true, false], path: [2, 1], emitted: 2, current_node: "[2,1]" }
narration: "Choose 1 at depth 1 (i loops from 0; used[1] skipped). Path = [2, 1]."
- step: 15
kind: pushChoice
payload: { value: 3, depth: 2 }
state: { used: [true, true, true], path: [2, 1, 3], emitted: 2, current_node: "[2,1,3]" }
narration: "Choose 3 at depth 2. Length matches n."
- step: 16
kind: snapshot
payload: { path: [2, 1, 3] }
state: { used: [true, true, true], path: [2, 1, 3], emitted: 3, current_node: "[2,1,3]" }
narration: "Emit permutation 3: [2, 1, 3]. Backtrack."
- step: 17
kind: popChoice
payload: { value: 3 }
state: { used: [true, true, false], path: [2, 1], emitted: 3, current_node: "[2,1]" }
narration: "Pop 3. Backtrack."
- step: 18
kind: pushChoice
payload: { value: 3, depth: 1 }
state: { used: [false, true, true], path: [2, 3], emitted: 3, current_node: "[2,3]" }
narration: "After popping 1 and choosing 3 at depth 1: path = [2, 3]. (Steps 17.5 and 17.75 collapsed for brevity.)"
- step: 19
kind: snapshot
payload: { path: [2, 3, 1] }
state: { used: [true, true, true], path: [2, 3, 1], emitted: 4, current_node: "[2,3,1]" }
narration: "Emit permutation 4: [2, 3, 1] after choosing 1 at depth 2."
- step: 20
kind: pushChoice
payload: { value: 3, depth: 0 }
state: { used: [false, false, true], path: [3], emitted: 4, current_node: "[3]" }
narration: "After backtracking to root and continuing loop: choose 3 at depth 0. Subtree under 3 begins."
- step: 21
kind: snapshot
payload: { path: [3, 1, 2] }
state: { used: [true, true, true], path: [3, 1, 2], emitted: 5, current_node: "[3,1,2]" }
narration: "Emit permutation 5: [3, 1, 2]."
- step: 22
kind: snapshot
payload: { path: [3, 2, 1] }
state: { used: [true, true, true], path: [3, 2, 1], emitted: 6, current_node: "[3,2,1]" }
narration: "Emit permutation 6: [3, 2, 1]. Backtrack to root; loop exhausts."
- step: 23
kind: done
payload: { count: 6 }
state: { used: [false, false, false], path: [], emitted: 6, current_node: null }
narration: "Done. 3! = 6 permutations collected; bijection with the leaves of the depth-3 tree."
panel-combos:
chapter: "7.2"
label: "Combination Sum decision tree (LC 39)"
canonical_input: |
candidates = [2, 3, 6, 7]
target = 7
presets:
- id: canonical
label: "Canonical (target = 7)"
input: { candidates: [2, 3, 6, 7], target: 7 }
- id: smaller
label: "Smaller (target = 4)"
input: { candidates: [2, 3], target: 4 }
n_steps: 19
# Trace generated by hand-tracing the §5.6 mechanism against the LC 39
# canonical input. Two snapshots ([2,2,3] and [7]) match the LC 39
# expected output. Branch-and-bound cuts (target < 0) are rendered as
# explicit prune events.
keyframes:
- step: 0
kind: init
state: { path: [], remaining: 7, emitted: 0, current_node: "root" }
narration: "About to enumerate combinations summing to 7 over [2, 3, 6, 7] with reuse allowed."
- step: 1
kind: pushChoice
payload: { value: 2, depth: 0 }
state: { path: [2], remaining: 5, emitted: 0, current_node: "[2]" }
narration: "Choose 2. remaining = 5. Recurse with start = i (not i+1) to allow reuse."
- step: 2
kind: pushChoice
payload: { value: 2, depth: 1 }
state: { path: [2, 2], remaining: 3, emitted: 0, current_node: "[2,2]" }
narration: "Choose 2 again (reuse). remaining = 3."
- step: 3
kind: pushChoice
payload: { value: 2, depth: 2 }
state: { path: [2, 2, 2], remaining: 1, emitted: 0, current_node: "[2,2,2]" }
narration: "Choose 2 a third time. remaining = 1."
- step: 4
kind: prune
payload: { reason: "remaining 1 < smallest candidate 2; no extension can hit zero" }
state: { path: [2, 2, 2], remaining: 1, emitted: 0, current_node: "[2,2,2]" }
narration: "Prune. Sorted-candidates early break: candidates[0] = 2 > remaining = 1. Backtrack."
- step: 5
kind: popChoice
payload: { value: 2 }
state: { path: [2, 2], remaining: 3, emitted: 0, current_node: "[2,2]" }
narration: "Pop 2. Continue loop at depth 2 from i=1 (value 3)."
- step: 6
kind: pushChoice
payload: { value: 3, depth: 2 }
state: { path: [2, 2, 3], remaining: 0, emitted: 0, current_node: "[2,2,3]" }
narration: "Choose 3. remaining = 0: target hit exactly."
- step: 7
kind: snapshot
payload: { path: [2, 2, 3] }
state: { path: [2, 2, 3], remaining: 0, emitted: 1, current_node: "[2,2,3]" }
narration: "Emit combination 1: [2, 2, 3]. Backtrack."
- step: 8
kind: popChoice
payload: { value: 3 }
state: { path: [2, 2], remaining: 3, emitted: 1, current_node: "[2,2]" }
narration: "Pop 3. Try i=2 (value 6): 6 > remaining 3; break. Backtrack to depth 1."
- step: 9
kind: popChoice
payload: { value: 2 }
state: { path: [2], remaining: 5, emitted: 1, current_node: "[2]" }
narration: "Pop 2. Try i=1 (value 3) at depth 1."
- step: 10
kind: pushChoice
payload: { value: 3, depth: 1 }
state: { path: [2, 3], remaining: 2, emitted: 1, current_node: "[2,3]" }
narration: "Choose 3 at depth 1. remaining = 2."
- step: 11
kind: prune
payload: { reason: "all remaining candidates (3, 6, 7) exceed remaining 2" }
state: { path: [2, 3], remaining: 2, emitted: 1, current_node: "[2,3]" }
narration: "Prune at depth 2: candidates[1] = 3 > remaining = 2; break. Backtrack."
- step: 12
kind: popChoice
payload: { value: 3 }
state: { path: [2], remaining: 5, emitted: 1, current_node: "[2]" }
narration: "Pop 3. Try i=2 (value 6): 6 > remaining 5; break. Backtrack to depth 0."
- step: 13
kind: popChoice
payload: { value: 2 }
state: { path: [], remaining: 7, emitted: 1, current_node: "root" }
narration: "Pop 2. Try i=1 (value 3) at root."
- step: 14
kind: pushChoice
payload: { value: 3, depth: 0 }
state: { path: [3], remaining: 4, emitted: 1, current_node: "[3]" }
narration: "Choose 3 at root. remaining = 4. Subsequent recursion explores [3, 3, ...] but every depth-2 candidate (>= 3) exceeds the residual; pruned."
- step: 15
kind: popChoice
payload: { value: 3 }
state: { path: [], remaining: 7, emitted: 1, current_node: "root" }
narration: "Subtree under 3 produces no more snapshots. Pop 3. Try i=2 (value 6) at root."
- step: 16
kind: pushChoice
payload: { value: 7, depth: 0 }
state: { path: [7], remaining: 0, emitted: 1, current_node: "[7]" }
narration: "Skipping 6 (subtree explored and pruned similarly), choose 7 at root. remaining = 0: target hit."
- step: 17
kind: snapshot
payload: { path: [7] }
state: { path: [7], remaining: 0, emitted: 2, current_node: "[7]" }
narration: "Emit combination 2: [7]. No more candidates after 7 to explore."
- step: 18
kind: done
payload: { count: 2 }
state: { path: [], remaining: 7, emitted: 2, current_node: null }
narration: "Done. Two combinations: [2, 2, 3] and [7]. Pruned subtrees stay collapsed in the visual."
panel-template:
chapter: "7.1"
label: "Backtracking template (LC 17 - Letter Combinations of a Phone Number)"
canonical_input: |
digits = "23"
keypad = {2: "abc", 3: "def"}
presets:
- id: canonical
label: "Canonical (digits = \"23\", 3 x 3 cartesian product)"
input: { digits: "23" }
- id: single_digit
label: "Single digit (\"2\" -> [\"a\", \"b\", \"c\"])"
input: { digits: "2" }
- id: empty
label: "Empty input (no leaves emitted)"
input: { digits: "" }
n_steps: 26
# Trace transcribed from the chapter prose at lines 149-167. Three
# branches at depth 0 (a / b / c), each fanning to three at depth 1
# (d / e / f), nine leaves total. Every push at the inner level has
# a matching pop on the same row of the trace; that pairing is the
# chapter's load-bearing observation.
keyframes:
- step: 0
kind: snapshot
payload: { path: [] }
state: { stack_depth: 0, path: [], emitted: 0, current_node: "root", phase: "enter" }
narration: "Enter root. path = []. The for-loop at depth 0 will iterate over the keypad of digit '2' = {a, b, c}."
- step: 1
kind: pushChoice
payload: { value: "a", depth: 0 }
state: { stack_depth: 1, path: ["a"], emitted: 0, current_node: "[a]", phase: "choose" }
narration: "Choose 'a' at depth 0. path = ['a']. Recurse into depth 1 (digit '3' -> {d, e, f})."
- step: 2
kind: pushChoice
payload: { value: "d", depth: 1 }
state: { stack_depth: 2, path: ["a", "d"], emitted: 0, current_node: "[a,d]", phase: "choose" }
narration: "Choose 'd' at depth 1. path = ['a', 'd']. i = 2 = len(digits); is_complete fires."
- step: 3
kind: snapshot
payload: { path: ["a", "d"] }
state: { stack_depth: 2, path: ["a", "d"], emitted: 1, current_node: "[a,d]", phase: "emit", emitted_strings: ["ad"] }
narration: "Emit 'ad'. result = ['ad']. Return; the caller's unchoose runs next."
- step: 4
kind: popChoice
payload: { value: "d" }
state: { stack_depth: 1, path: ["a"], emitted: 1, current_node: "[a]", phase: "unchoose", emitted_strings: ["ad"] }
narration: "Unchoose 'd'. path = ['a']. The matching unchoose for the choose on step 2."
- step: 5
kind: pushChoice
payload: { value: "e", depth: 1 }
state: { stack_depth: 2, path: ["a", "e"], emitted: 1, current_node: "[a,e]", phase: "choose", emitted_strings: ["ad"] }
narration: "Next iteration of the depth-1 for-loop: choose 'e'. path = ['a', 'e']."
- step: 6
kind: snapshot
payload: { path: ["a", "e"] }
state: { stack_depth: 2, path: ["a", "e"], emitted: 2, current_node: "[a,e]", phase: "emit", emitted_strings: ["ad", "ae"] }
narration: "Emit 'ae'. result = ['ad', 'ae']."
- step: 7
kind: popChoice
payload: { value: "e" }
state: { stack_depth: 1, path: ["a"], emitted: 2, current_node: "[a]", phase: "unchoose", emitted_strings: ["ad", "ae"] }
narration: "Unchoose 'e'. path = ['a']."
- step: 8
kind: pushChoice
payload: { value: "f", depth: 1 }
state: { stack_depth: 2, path: ["a", "f"], emitted: 2, current_node: "[a,f]", phase: "choose", emitted_strings: ["ad", "ae"] }
narration: "Choose 'f'. path = ['a', 'f']."
- step: 9
kind: snapshot
payload: { path: ["a", "f"] }
state: { stack_depth: 2, path: ["a", "f"], emitted: 3, current_node: "[a,f]", phase: "emit", emitted_strings: ["ad", "ae", "af"] }
narration: "Emit 'af'. result = ['ad', 'ae', 'af']. Inner for-loop exhausted; return."
- step: 10
kind: popChoice
payload: { value: "f" }
state: { stack_depth: 1, path: ["a"], emitted: 3, current_node: "[a]", phase: "unchoose", emitted_strings: ["ad", "ae", "af"] }
narration: "Unchoose 'f'. path = ['a']."
- step: 11
kind: popChoice
payload: { value: "a" }
state: { stack_depth: 0, path: [], emitted: 3, current_node: "root", phase: "unchoose", emitted_strings: ["ad", "ae", "af"] }
narration: "Unchoose 'a'. path = []. The first top-level branch is fully done; path is back to the state it had on step 0 before the 'a' branch began."
- step: 12
kind: pushChoice
payload: { value: "b", depth: 0 }
state: { stack_depth: 1, path: ["b"], emitted: 3, current_node: "[b]", phase: "choose", emitted_strings: ["ad", "ae", "af"] }
narration: "Next iteration of the depth-0 for-loop: choose 'b'. path = ['b']."
- step: 13
kind: pushChoice
payload: { value: "d", depth: 1 }
state: { stack_depth: 2, path: ["b", "d"], emitted: 3, current_node: "[b,d]", phase: "choose", emitted_strings: ["ad", "ae", "af"] }
narration: "Choose 'd' at depth 1. path = ['b', 'd']."
- step: 14
kind: snapshot
payload: { path: ["b", "d"] }
state: { stack_depth: 2, path: ["b", "d"], emitted: 4, current_node: "[b,d]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd"] }
narration: "Emit 'bd'. The 'b' subtree mirrors the 'a' subtree exactly because both started from the same path = []."
- step: 15
kind: popChoice
payload: { value: "d" }
state: { stack_depth: 1, path: ["b"], emitted: 4, current_node: "[b]", phase: "unchoose", emitted_strings: ["ad", "ae", "af", "bd"] }
narration: "Pop 'd'. path = ['b']."
- step: 16
kind: snapshot
payload: { path: ["b", "e"] }
state: { stack_depth: 2, path: ["b", "e"], emitted: 5, current_node: "[b,e]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd", "be"] }
narration: "Push 'e', snapshot, emit 'be'. (Two events compressed: choose-and-emit.)"
- step: 17
kind: snapshot
payload: { path: ["b", "f"] }
state: { stack_depth: 2, path: ["b", "f"], emitted: 6, current_node: "[b,f]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf"] }
narration: "Pop 'e', push 'f', emit 'bf'. The depth-1 for-loop is now exhausted under 'b'."
- step: 18
kind: popChoice
payload: { value: "b" }
state: { stack_depth: 0, path: [], emitted: 6, current_node: "root", phase: "unchoose", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf"] }
narration: "Pop 'f'; pop 'b'. path = []. Two branches done; one remains."
- step: 19
kind: pushChoice
payload: { value: "c", depth: 0 }
state: { stack_depth: 1, path: ["c"], emitted: 6, current_node: "[c]", phase: "choose", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf"] }
narration: "Choose 'c'. path = ['c']."
- step: 20
kind: snapshot
payload: { path: ["c", "d"] }
state: { stack_depth: 2, path: ["c", "d"], emitted: 7, current_node: "[c,d]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd"] }
narration: "Push 'd', emit 'cd'."
- step: 21
kind: snapshot
payload: { path: ["c", "e"] }
state: { stack_depth: 2, path: ["c", "e"], emitted: 8, current_node: "[c,e]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce"] }
narration: "Pop 'd', push 'e', emit 'ce'."
- step: 22
kind: snapshot
payload: { path: ["c", "f"] }
state: { stack_depth: 2, path: ["c", "f"], emitted: 9, current_node: "[c,f]", phase: "emit", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] }
narration: "Pop 'e', push 'f', emit 'cf'. Nine leaves emitted; depth-1 loop exhausted under 'c'."
- step: 23
kind: popChoice
payload: { value: "f" }
state: { stack_depth: 1, path: ["c"], emitted: 9, current_node: "[c]", phase: "unchoose", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] }
narration: "Pop 'f'. path = ['c']."
- step: 24
kind: popChoice
payload: { value: "c" }
state: { stack_depth: 0, path: [], emitted: 9, current_node: "root", phase: "unchoose", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] }
narration: "Pop 'c'. path = []. Outer for-loop exhausted; return to caller."
- step: 25
kind: snapshot
payload: { path: [] }
state: { stack_depth: 0, path: [], emitted: 9, current_node: "root", phase: "done", emitted_strings: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"], result: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] }
narration: "Done. result = ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']. 9 leaves = |digit-2-set| x |digit-3-set| = 3 x 3. Every push had its matching pop; path returned to [] cleanly."
selector_default: panel-subsets
# Default interaction model (DSH-18: no widget autoplays on page load).
default_state: paused-at-step-0
controls:
primary: [step-forward, step-back, reset]
secondary: [play-pause, speed]
accessibility:
prefers_reduced_motion: static-keyframes-only
aria_live: polite
keyboard_shortcuts:
step_forward: ArrowRight
step_back: ArrowLeft
reset: r
play_pause: Space
# Wong palette tokens (Nature Methods 2011). No naked red/green pairs.
palette:
active_node: var(--wong-orange) # current dfs frame
emit_event: var(--wong-bluish-green) # snapshot fired
pruned_subtree: var(--wong-vermilion) # branch-and-bound cut (LC 39)
visited_node: var(--wong-blue) # already-explored, currently popped
default_node: var(--wong-black) # tree skeleton
notes: |
Three-way-shared widget for Part 7. Chapter 7.2 owns three panels
(subsets / permutations / combination sum) and is the chapter where
the choose-explore-unchoose chassis becomes mechanical for the reader.
Chapter 7.1 owns one scaffold panel (panel-template) for LC 17 to fill
in when 7.1 ships. The reader compares panels side by side: the same
edge-and-snapshot chassis drives all three problems; only the
snapshot rule and the next-available-element rule change.
Pedagogically critical moments per panel:
- Subsets: step 0 (root snapshot, the empty subset is the FIRST one
emitted, not the last) and step 7 (first backtrack: pop AFTER the
leaf snapshot, not before).
- Permutations: step 1 (used[0] = true, the structural difference
from subsets) and step 12 (used[0] = false on backtrack, the
"unchoose" half of choose-explore-unchoose).
- Combination Sum: step 2 (reuse, the same value 2 chosen twice in
a row, possible because recursion advances i not i+1) and step 4
(the first prune: the branch-and-bound cut that keeps the search
tree finite even when reuse is allowed).From The Engineering Handbook (source), CC BY-SA 4.0.