子集生成

回溯与搜索 · 决策树 DFS

枚举一个集合的所有子集

给一个集合 {1, 2, 3}，列出它的全部子集（包括空集和它自己）——这些子集的集合叫幂集。n 个元素共有 2^n 个子集。怎么不重不漏地枚举出来？这是回溯的又一经典范例，而且它把回溯的另一半心智模型——决策树——展现得最清楚。

把「选还是不选」画成一棵决策树

对每个元素，只有两种选择：选它，或不选它。于是「依次对 1、2、3 做决定」就构成一棵二叉决策树：从根出发，每往下一层就对一个元素拍板选/不选，走到叶子（三个元素都决定完）时，一路上「选」进来的元素就凑成了一个子集。2^3 = 8 个叶子，恰好对应 8 个子集。

回溯就是深度优先地走遍这棵决策树：先一头扎到底（一路「选」），到叶子记下一个子集；然后退回上一步，把最后那个决定从「选」改成「不选」，再往下走……如此前进 → 到底 → 回退换选择，直到整棵树走完。「退回上一步、撤销刚才的选择」正是回溯一词的由来。

下面是元素 [1, 2, 3] 的完整决策树。点「下一步」逐步看：当前节点琥珀高亮，当前这条根到底的路径连起来高亮（就是此刻递归栈里的选择）；每条边标着这一步的决定（选 k / 跳过 k）；走到叶子就把它标绿、记录一个子集；一条子树走完就回溯去试另一条分支。右侧代码随每一步同步高亮。

从空集 ∅ 出发，对每个元素依次决定「选」或「不选」

1function subsets(nums: number[]): number[][] {
const res: number[][] = [];
const cur: number[] = [];
const backtrack = (i: number): void => {
  if (i === nums.length) {
    res.push([...cur]);
    return;
  }
  cur.push(nums[i]);       // 选 nums[i]
  backtrack(i + 1);
  cur.pop();               // 撤销（回溯）
  backtrack(i + 1);        // 不选 nums[i]
};
backtrack(0);
return res;
16}

元素1 2 3

当前子集∅

已收集0 / 8

1 / 31

注意这棵决策树的形状：每个内部节点分出「选 / 不选」两枝，深度 n、叶子 2^n——这正是子集数为 2^n 的直观解释。回溯并不比「暴力枚举全部 2^n 种情况」更快（子集问题本就有指数多个答案），它的价值在于用一套统一的「递归 + 撤销」框架，系统地、不重不漏地走遍解空间。

决策树：回溯的通用心智模型

几乎所有回溯题都是在一棵决策树上做 DFS，区别只在「每一步有哪些选择」「什么时候剪枝」：
子集：每个元素选 / 不选（本页）。组合：从剩余元素里挑，避免重复。
全排列：每步从没用过的元素里挑一个。组合总和：挑到和超标就剪枝回退。
连 N 皇后也是——只是它的决策树画在棋盘上（每列选哪一行）。

对比看：N 皇后用棋盘呈现「约束满足」的回溯，本页用决策树呈现「组合枚举」的回溯——两种视角，同一套 DFS + 剪枝 + 回退。

算法可视化

子集生成

枚举一个集合的所有子集

把「选还是不选」画成一棵决策树

决策树：回溯的通用心智模型