回溯

这篇是我做 78. Subsets · 子集 时整理的回溯（backtracking）笔记。一开始我能背模板，但说不清 path.pop() 到底在干嘛、为什么子集不会重复。后来配合动画一步步走，才真的看懂。 This is my note on backtracking, written while working on LeetCode 78 Subsets. At first I could recite the template, but I couldn’t explain what path.pop() was actually doing, or why subsets never come out duplicated. Stepping through it with animations is what finally made it click. 一句话总结本质： 回溯就是在一棵决策树上做 DFS。每走一步都是三件事：做选择（append）→ 往下走（递归）→ 撤销选择（pop）。撤销是为了回到岔路口，让下一个选项拿到一条干净的 path。 Backtracking is DFS on a decision tree. Every step is three moves: choose (append) → explore (recurse) → un-choose (pop). Un-choosing walks you back to the fork, so the next option starts from a clean path. ...

这篇接着上一篇 回溯学习笔记。我在给 nums = [1,2,3,4] 画 78. Subsets 的递归树时，好几次把节点和循环对错了位置，比如把 range(2,4) 安到 [1,2,3] 头上。这篇把怎么对齐整理清楚。 This follows my earlier backtracking note. While drawing the recursion tree of LC 78 Subsets for nums = [1,2,3,4], I kept attaching loops to the wrong nodes, for example putting range(2,4) on [1,2,3]. This note is about how to line them up. 一句话总结： 节点的 start 是几，它自己的循环就是 range(几, 4)。 循环里的每个 i 产生一个孩子，孩子的 start 是 i + 1。 A node’s own loop always uses its own start: range(start, 4). Each i in that loop makes one child, and that child’s start is i + 1. ...