回溯算法题型总结

方法

先手动模拟解题流程， 得到一个不变的流程， 这个不变的流程就是递归函数的语义.

[👍](LeetCode 77 组合 - 回溯解法.md)可以看到， 求解递归问题时可以先手动模拟得到 不变的流程， 上述题目中为 “不断地从某一区间选一个数加入到path中”， 这个不变的流程就是递归函数的语义.

• 例如： [组合](LeetCode 77 组合 - 回溯解法.md)，模拟得到 {从某一区间内选一个数加入到path， 再从这个数下一位开始到max中选数加入path}是不变的， 不断重复这个不变的流程， 而变的只是 {从哪里开始}. 不变的应为函数的语义，这些变的应为函数的参数.

求集合，子集的问题函数的语义就是 从index 到最后选个值加入path，再从选的值后面开始再选;
求分割的问题函数的语义就是 从index开始分割出来一部分加入path，再分割后面的.

• 2026-01-24
  • 在for循环中不要控制下一层参数的范围，留给下一层的return，比如单词搜索，for中不要看 newi newj 是否合法，留给下一层，当然顺序要对，先判断index直接返回true，再看其他

分类

组合

👍 函数语义：从index 到max 选数加入到path

[组合](LeetCode 77 组合 - 回溯解法.md) [组合总和](LeetCode 39 组合总和 - 回溯解法.md) [组合总和2](LeetCode 40 组合总和 II - 回溯解法.md)

分割

👍 函数语义：从index开始切取前面一部分合法串加入到path，直到切完。

[分割回文串](LeetCode 131 分割回文串 - 回溯解法.md) [复原ip地址](LeetCode 93 复原 IP 地址 - 回溯解法.md)

子集

👍 函数语义：从index到max选值加入path。 但和组合不同，这里不需要显式return。

[子集](LeetCode 78 子集 - 回溯解法.md) [子集2](LeetCode 90 子集 II - 回溯解法.md)

[递增子序列](LeetCode 491 递增子序列 - 回溯解法.md) ：函数语义：从index到最后选择一个合法值加入到path。

排列

👍 函数语义：从0到最后选之前未选过的值加入path。

[全排列](LeetCode 46 全排列 - 回溯解法.md) [全排列2](LeetCode 47 全排列 II - 回溯解法.md)

注意

✖️[分割回文串](LeetCode 131 分割回文串 - 回溯解法.md) :在 if 判断的 return 位置不要对 path 进行 push 操作，因为没有与之对应 pop 操作， 这会导致 path pop不干净.

✖️[子集](LeetCode 78 子集 - 回溯解法.md): 注意不要return，到最后一层，for循环不会执行， 隐式 return.

✖️[递增子序列](LeetCode 491 递增子序列 - 回溯解法.md) ：last 不能满足去重了， 使用 use 数组。

✖️[全排列](LeetCode 46 全排列 - 回溯解法.md)：设置全局变量，及时更新全局变量来控制 push哪些值。

✖️[全排列2](LeetCode 47 全排列 II - 回溯解法.md)：重点在于去重， 有个bug：last 设置的位置。

✖️❗[解数独](LeetCode 37 解数独 - 回溯解法.md)：直接在传入的参数上进行操作，不用再本地设置 path 等。

• 为什么要设置 write 返回值 为 bool 而非 void 。
• 是如何防止正确的状态被重写的。