刷题小记9：回溯

回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题

N个数按一定规则全排列，有几种排列方式

77.组合

组合

startIndex 就是防止出现重复的组合

剪枝优化

如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，就没有必要搜索了

优化过程如下：

已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2之前开始搜索都是合理的，可以是组合[2, 3, 4]。

优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

216. 组合总和 III

剪枝

已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。

17.电话号码的字母组合

电话号码的字母组合

定义一个二维数组，用来映射按键数字和字母

index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度

39.组合总和

组合总和

和77.组合，216.组合总和III的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

关于startIndex

如果是一个集合来求组合的话，就需要startIndex

例如：77.组合，216.组合总和III。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

例如：

以上只在讨论组合时

剪枝

       if (sum >= target) {
           if (sum == target) {
              result.push_back(path);
           }
       return;
       }

对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做文章

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

40.组合总和 II

组合总和 II

这道题目和39.组合总和如下区别：

本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，39.组合总和是无重复元素的数组candidates。

要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

力扣题解（LeetCode）

分割问题

131.分割回文串

分割回文串

递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的

递归终止条件：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

时间复杂度: O(n * 2^n)
空间复杂度: O(n^2)

93. 复原 IP 地址

复原 IP 地址

代码随想录

子集问题

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和子集{2,1}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

78.子集

子集

当 startIndex已经大于数组的长度了，就终止了，因为没有元素可取了

排列问题

46.全排列

全排列

boolean[] used数组记录元素是否被使用过，不使用 startIndex

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1

47.全排列 II

全排列 II

去重的关键在于回溯法中的以下几行代码：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; }

2.1. 排序

首先，数组在调用 Arrays.sort(nums) 后被排序。这样做的目的是为了确保相同的元素相邻，方便判断和去重。

2.2. 跳过重复元素

在回溯过程中，当我们遍历每一个可能的数字 nums[i] 时，首先会检查当前数字与前一个数字 nums[i-1] 是否相等：
- if (i > 0 && nums[i] == nums[i - 1])：这部分检查当前数字是否与前一个数字相同。如果相同，可能会有重复的排列出现。
接下来的条件 used[i - 1] == false 用来确保在同一树层（即同一递归深度）中，只有第一个出现的相同数字被处理。具体来说：
- 如果 used[i - 1] 是 false，表示在同一层级中前一个数字（即 nums[i-1]）未被使用过，那么当前数字 nums[i] 也不应该被使用，从而跳过该循环。这确保了只有第一次遇到的相同元素会被使用。

2.3. 使用标记

used[i] 用于标记当前数字是否已经被使用：
- 当 used[i] 为 false 时，表示该数字可以被使用，之后将其标记为 true，表示已使用。在完成当前路径的构造后，标记恢复为 false，以便于其他路径的生成。

22. 括号生成

括号生成

记录左括号和右括号用了几个

右括号数量不能大于左括号数量

左括号数量等于右括号时，收集结果

棋盘问题

79.单词搜索

单词搜索

和岛屿问题的区别在于,需要取消染色。

51. N皇后

N 皇后

37.解数独

额外题目

90. 子集 II 和40.组合总和 II 一样，排序后树层去重

491. 非递减子序列

秒客网