回溯专题
本文最后更新于：2023年3月16日 上午
总结：
回溯其实是一种大而全的动规，把n-1的结果和第n个元素进行特殊的操作，即可得到结果
46的全排列，引入flag进行元素排除，他的算子方式通过for循环执行的，这种可以是无序的结果元素的顺序跟输入可能不一致
39的组合和，引入n进行天然的元素排除+算子，这种特点是有顺序，算子是选择当前或者不选，这种结果通过结果元素属性和输入是一致的
回溯算法总结
- 递进式，这种题目不走回头路，只会选择当前及其后面的元素，所以不用循环，只需要考虑当前的元素选还是不选的问题。类似的题目77、78
- 遍历式，这种是可以走回头路的，是在for循环中，不断从头开始进行寻找，可以用一个布尔类型的数组来判断当前的元素是否被选中，类似的题目46、47、79
- 批量递进式，在递归时一次性地处理重复数，通常用于去重，类似题目40
回溯去重算法总结
回溯的去重算法
保证重复元素，从左到右只选择第一次出现的
1
2
3
4i > 0 && nums[i - 1] == nums[i] && !flags[i - 1]
[1,2,2,2,3]
只会选择最左边出现的2，以及以它打头的[2,2]和[2,2,2]把重复的元素合并一起计算
1
2
3
4
5
6
7
8int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
for (int i = 1; i <= most; ++i) {
sequence.add(freq.get(pos)[0]);
dfs(pos + 1, rest - i * freq.get(pos)[0]);
}
for (int i = 1; i <= most; ++i) {
sequence.remove(sequence.size() - 1);
}
[1,2,2,3]
第一种方式，2,2并不要求放在一起，可以是2,1,2或者2,3,2这种，它只对打头的2做出要求，必须是最左边的
lt47这种写法，就允许不同的2分开。对于lt90这种写法就重复的2就是放在一起的，
第二种方式，2,2需要放在一起，它更像是作为一个整体，类似lt40
待验证，lt40和lt90，算法互通，lt90是找子集，lt40是求符合要求的组合，本质是找一种特殊的子集
优化思路：通常是进行一定的剪枝，即根据特定的场景，不在进行递归而是直接返回，减少回溯的次数从而优化
时间复杂度通常都是(n * n!)
解题的核心就是找算子的种类，只要找到算子，然后在算子前面添加元素，在算子后面删除元素，问题解决！
- 数组当前元素加或者不加
- 数组当前一部分元素加或者不加
- 方阵的四方方向
LeetCode39 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
1 | |
LeetCode40 组合总和2z(nonono)
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
1 | |
由于我们需要求出所有和为 target 的组合，并且每个数只能使用一次，因此我们可以使用递归 + 回溯的方法来解决这个问题：
- 我们用 dfs(pos,rest) 表示递归的函数，其中 pos 表示我们当前递归到了数组 candidates 中的第 pos 个数，而 rest 表示我们还需要选择和为 rest 的数放入列表作为一个组合；
- 对于当前的第 pos 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用 dfs(pos+1,rest−candidates[pos]) 进行递归，注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数，那么我们调用 dfs(pos+1,rest) 进行递归；
- 在某次递归开始前，如果 rest 的值为 0，说明我们找到了一个和为 target 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。
上述算法就是一个标准的递归 + 回溯算法，但是它并不适用于本题。这是因为题目描述中规定了解集不能包含重复的组合，而上述的算法中并没有去除重复的组合。
例如当 candidates=[2,2]，target=2 时，上述算法会将列表 [2] 放入答案两次。
因此，我们需要改进上述算法，在求出组合的过程中就进行去重的操作。我们可以考虑将相同的数放在一起进行处理，也就是说，如果数 x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0,1,⋯,y 次 x 的递归函数。这样我们就不会得到重复的组合。具体地：
我们使用一个哈希映射（HashMap）统计数组 candidates 中每个数出现的次数。在统计完成之后，我们将结果放入一个列表 freq 中，方便后续的递归使用。
- 列表 freq 的长度即为数组 candidates 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。
在递归时，对于当前的第 pos 个数，它的值为 freq[pos][0]，出现的次数为 freq[pos][1]，那么我们可以调用
dfs(pos+1,rest−i×freq[pos][0])
即我们选择了这个数 i 次。这里 i 不能大于这个数出现的次数，并且 i×freq[pos][0] 也不能大于 rest。同时，我们需要将 i 个 freq[pos][0] 放入列表中。
这样一来，我们就可以不重复地枚举所有的组合了。
我们还可以进行什么优化（剪枝）呢？一种比较常用的优化方法是，我们将 freq 根据数从小到大排序，这样我们在递归时会先选择小的数，再选择大的数。这样做的好处是，当我们递归到 dfs(pos,rest) 时，如果 freq[pos][0] 已经大于 rest，那么后面还没有递归到的数也都大于 rest，这就说明不可能再选择若干个和为 rest 的数放入列表了。此时，我们就可以直接回溯。
LeetCode46 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
1 | |
示例 2：
1 | |
示例 3：
1 | |
LeetCode47 全排列2
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
1 | |
示例 2：
1 | |
LeetCode77 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
1 | |
LeetCode78 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1 | |
示例 2：
1 | |
LeetCode79 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
1 | |
LeetCode90 子集2
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
1 | |
示例 2：
1 | |
LeetCode131 分隔回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
1 | |
示例 2：
1 | |
LeetCode216 组合总和3
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
1 | |
示例 2:
1 | |
示例 3:
1 | |
LeetCode131 分割回文子串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
1 | |
示例 2：
1 | |