LeetCode 笔记：回溯的两种类型与 index 类型的选择

总结

回溯有两种类型：排列组合和子集问题。当然还有一些特殊模型，比如可重复使用等等，只需要在这两个模型上做一点点微调即可。

两种类型的本质区别在于：每个步骤是否独立。比如高中数学中的 C 在 n 中选几个，这就是有上下文关联的：这次取了 A，下次不能再取一次 A 了。这就是“子集问题”，这种问题一般使用 startIndex 来定位“从哪里开始选”，确保不会重新选取。反之如果各个步骤是独立的，比如每次所选取的元素不是在一个集合中的（比如电话号码问题），就可以使用“我这个位置要选择什么？”的思想来做，只要使用 index 来确定“我正在选第几个”就可以了。这就是“排列组合”问题。

还有一个区分的维度就是顺序是否重要，如果顺序重要，即使它上下文关联，也应该用排列组合思维来做，可以这样想，如果顺序重要，我就可以用“我这个位置要选择什么”来思考，因为不同位置选相同的元素，这是不同的答案。如果顺序不重要，去思考“我这个位置选择什么”是没有意义的。这个典型例子就是“全排列”那一道题。当然既然使用了步骤独立的方法来处理步骤不独立的问题（全排列明显是步骤不独立的问题，元素不能重复），就要再用一些补丁解决，这道题就是用了一个 used 数组来解决。

下面是 AI 给出的详细分析。

核心区别：问题的本质

index 和 startIndex 的使用，取决于回溯问题是在解决 “排列组合” 问题还是 “子集/组合” 问题。

startIndex 用于 “组合/子集” 类问题 (Combinations / Subsets)

问题特征: 从一个集合中选取若干元素组成一个新的集合，元素的顺序不重要，且 不能重复选取同一个元素。
典型例子:
- LeetCode 77. Combinations: 从 1 到 n 中选 k 个数。
- LeetCode 78. Subsets: 找出一个集合的所有子集。
- LeetCode 90. Subsets II (有重复元素)。
- LeetCode 40. Combination Sum II (每个数只能用一次)。
startIndex 的作用: 它是为了 避免产生重复的组合。通过规定下一次递归只能从 startIndex（或 i+1）开始选择，我们强制了一个选择的顺序（例如，只能往后选，不能回头选），从而保证了像 [1, 2] 和 [2, 1] 这样的重复组合只会出现一次。

伪代码示例 (组合问题):

void backtrack(int startIndex, ...) {
    // ... 收集结果 ...

    for (int i = startIndex; i < candidates.length; i++) {
        // ... 做选择 ...
        path.add(candidates[i]);
        // 关键：传入 i + 1，保证下次从下一个位置开始选
        backtrack(i + 1, ...);
        // ... 撤销选择 ...
        path.removeLast();
    }
}

index 用于 “排列/分步决策” 类问题 (Permutations / Step-by-step decision)

问题特征: 问题可以被分解成 多个独立的步骤，每一步都需要从一个 独立的选项集合 中做出选择，最终将所有步骤的选择连接起来构成一个完整解。每一步的选择范围和之前步骤的选择没有直接的“去重”关系。
典型例子:
- **LeetCode 17. Letter Combinations of a Phone Number
  - 第 1 步：为第一个数字（如 ‘2’）选择一个字母（’a’, ‘b’, or ‘c’）。
  - 第 2 步：为第二个数字（如 ‘3’）选择一个字母（’d’, ‘e’, or ‘f’）。
  - …以此类推。
  - 注意：第 2 步的选择范围 (def) 和第 1 步的选择 (abc) 是完全独立的。
- LeetCode 46. Permutations (全排列): 虽然也用回溯，但它更特殊，通常用 used 数组来标记元素是否被使用过，而不是 startIndex。但其本质也是分步决策：第 1 个位置放哪个数？第 2 个位置放哪个数？…
其他一些例子：
- LeetCode 47. 全排列 II (Permutations II): 在全排列模型上增加了“输入数组可能包含重复元素”的挑战，需要在剪枝时增加额外的逻辑来避免产生重复的排列结果。
- LeetCode 51. N皇后: 也可以看作一种排列问题。n 个皇后要占据 n 列，每一行的皇后占据哪一列，可以看作是 [0, 1, ..., n-1] 的一个排列。used 数组在这里就演变成了检查列冲突的 col_used 数组。
- LeetCode 784. 字母大小写全排列: 这是一个有趣的变体，决策不再是选择哪个元素，而是对每个字母字符决定是使用小写还是大写。
index 的作用: 它代表了当前正在处理 第几个步骤 或者 决策的层级。在你的电话号码问题中，index 就明确地表示“我们正在为 digits 字符串中的第 index 个数字做选择”。

伪代码示例 (电话号码问题):

void backtrack(int index, String digits) {
    // 如果所有数字都处理完了 (index 到达末尾)，说明一个解已构成
    if (index == digits.length()) {
        // ... 收集结果 ...
        return;
    }

    // 获取当前步骤 (第 index 个数字) 的所有选项
    String letters = map[digits.charAt(index) - '0'];

    // 遍历当前步骤的所有选项
    for (int i = 0; i < letters.length(); i++) {
        // ... 做选择 ...
        path.append(letters.charAt(i));
        // 关键：进入下一个步骤 (index + 1)
        backtrack(index + 1, digits);
        // ... 撤销选择 ...
        path.deleteCharAt(path.length() - 1);
    }
}

如何在做题前判断？

在读完题目后，问自己以下几个问题：

我是在一个集合里“挑选”元素吗？
- 如果是，并且元素的顺序无关紧要（例如 [1, 2] 和 [2, 1] 算同一个组合），那么这很可能是 组合/子集 问题。你应该使用 startIndex 来去重。
- 例如：“从数组 [1,2,3,4] 中找出所有大小为 2 的组合”。
问题是否可以被分解成一系列独立的步骤？
- 如果是，并且每一步都有自己独立的选项集，那么这很可能是 排列/分步决策 问题。你应该使用 index 来追踪当前进行到哪一步了。
- 例如：“输入是 “23”。第一步要从 ‘a’, ‘b’, ‘c’ 中选一个。第二步要从 ‘d’, ‘e’, ‘f’ 中选一个。这两步的选择是独立的。” 这就是典型的分步决策，用 index。
最终结果的长度是固定的吗？
- 在电话号码问题中，结果的长度总是等于输入 digits 字符串的长度。这通常是 分步决策 的一个强烈信号，因为你有固定数量的步骤要完成。
- 在组合/子集问题中，结果的长度通常是不固定的（子集问题）或由参数 k 决定（组合问题）。

总结

特征	`startIndex` (组合/子集类)	`index` (排列/分步决策类)
问题本质	从一个集合中挑选元素	完成多个独立的步骤
参数含义	下一轮递归应该从哪个起始位置开始挑选元素	当前正在处理第几个步骤或决策层级
for 循环	`for (int i = startIndex; ...)`	`for (char c : currentStepOptions)`
递归调用	`backtrack(i + 1, ...)`	`backtrack(index + 1, ...)`
典型问题	组合 (Combinations), 子集 (Subsets), 组合总和 (Combination Sum)	电话号码的字母组合 (Letter Combinations), 全排列 (Permutations)
核心目的	去重，确保每个组合只生成一次	推进，确保按顺序完成每一步决策

LeetCode

#LeetCode

LeetCode 笔记：回溯的两种类型与 index 类型的选择

https://idontwannago.cn/posts/57381/

作者

idontwannagoo

发布于

2025年11月1日

许可协议

Apple Music 和 Spotify 的选择上一篇

Obsidian 极速全端同步方案 Livesync 部署指南下一篇

LeetCode 笔记：回溯的两种类型与 index 类型的选择

LeetCode 笔记：回溯的两种类型与 index 类型的选择

目录

总结

核心区别：问题的本质

如何在做题前判断？

总结