491.递增子序列
本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。
代码随想录
视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili
方法1: 数组去重
class Solution {private List<Integer> path = new ArrayList<>();private List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {findSubsequencesHelper(nums, 0);return result; }public void findSubsequencesHelper(int[] nums, int starindex){if(path.size() > 1){result.add(new ArrayList<>(path));}if(starindex == nums.length){return;}int used[] = new int[201]; //使用set去重for(int i = starindex; i < nums.length; i++){if(used[nums[i] + 100] == 1){continue;}if(path.size() > 0 && nums[i] < path.get(path.size() - 1)){continue;}used[nums[i] + 100] = 1;path.add(nums[i]);findSubsequencesHelper(nums, i + 1);path.remove(path.size() - 1); }}}方法2：Map去重
class Solution {private List<Integer> path = new ArrayList<>();private List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {findSubsequencesHelper(nums, 0);return result; }public void findSubsequencesHelper(int[] nums, int starindex){if(path.size() > 1){result.add(new ArrayList<>(path));}if(starindex == nums.length){return;}Map<Integer,Integer> used = new HashMap<>(); //使用set去重for(int i = starindex; i < nums.length; i++){if(used.getOrDefault(nums[i],0) >= 1){continue;}if(path.size() > 0 && nums[i] < path.get(path.size() - 1)){continue;}used.put(nums[i], used.getOrDefault(nums[i],0) + 1);path.add(nums[i]);findSubsequencesHelper(nums, i + 1);path.remove(path.size() - 1); }}}方法3：Set去重
class Solution {private List<Integer> path = new ArrayList<>();private List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {findSubsequencesHelper(nums, 0);return result; }public void findSubsequencesHelper(int[] nums, int starindex){if(path.size() > 1){result.add(new ArrayList<>(path));}if(starindex == nums.length){return;}Set<Integer> used = new HashSet<>(); //使用set去重for(int i = starindex; i < nums.length; i++){if(used.contains(nums[i])){continue;}if(path.size() > 0 && nums[i] < path.get(path.size() - 1)){continue;}used.add(nums[i]);path.add(nums[i]);findSubsequencesHelper(nums, i + 1);path.remove(path.size() - 1); }}}总结
1.这道题和之前不同的地方在于去重的方法，以及我们需要将递增的序列放进path里面。所以我们需要将当前元素和path的最后一个元素比较，如果小于，就不能放回path里面。
2.去重的方法，还是树层需要去重，因为比如76789，第二个7需要考虑的组合，在第一个7里面都会考虑到。由于这道题不能对原数组排序，我们需要借助哈希数组来去重。这样就有三种方法：HashSet集合，我们只需要把使用过的数字add到数组里面，然后contains判断有没有加过这个数。HashMap，我们使用getOrDefault(Object key, V defaultValue)来统计当前元素出现的次数，如果大于等于1次，就continue跳过。或者直接数组(因为题目里面规定了-100<nums[i]<100)，所以我们可以创建一个201大小的数组，然后当前元素就和数组的下标对应好，如果元素出现了，就把used数组变成1。
3.注意used是不需要进行回溯的，因为used就是服务于本树层(集合)的，每个树层都会new一个新的used出来，这个是不会随着path进入到递归里面的。原来的boolean[] used标记数组的方法是需要进行回溯的，因为used标记数组要跟随path进入到下一层的，如果path路径进入到下一层就把used设置为true。只要进入递归就是true的状态，没有进入递归就是false。注意和本题的差别。
4.求子集问题(组合总和问题)一定要排序，即便使用的是set去重。set去重方法，每一层都要new 一个新的set集合出来，一个set负责一层的去重问题。不能把set定义为全局变量，这样不同层之间的set会相互影响。我们需要的是对一层去重，就需要一个单独的set负责一层。
5.碰到这类问题可以一开始就想好要排序，然后再结合问题考虑能不能排序，大部分问题都可以排序，但求递增序列那道题就不可以改变原数组的排序。所以能不能排序一定要考虑清楚，大部分问题都是可以排序的。
46.全排列
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
代码随想录
视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili
class Solution {private List<Integer> path = new ArrayList<>();private List<List<Integer>> result = new ArrayList<>();private int[] used ;public List<List<Integer>> permute(int[] nums) {used = new int[nums.length];permuteHelper(nums);return result;}public void permuteHelper(int[] nums){if(path.size() == nums.length){result.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){if(used[i] == 1){continue;}path.add(nums[i]);used[i] = 1;permuteHelper(nums);used[i] = 0;path.remove(path.size() - 1); }}}总结
1.这道题体现了排列和组合的不同之处。排列其实每次for循环都是nums数组，只是我们已经添加到path里面的元素不能使用，那怎么标记我们已经添加的元素呢？这时候就需要使用到一个used数组。如果该元素被添加到path路径里面(就是进入到下一层递归了)，那么就标记used为1。对整个数组for循环遍历的时候，我们碰到添加过的元素，就直接continue。
2.这里面记得对used数组和path路径进行回溯处理。
3.注意的两个点就是1.每层都是从0开始搜索而不是startIndex。2.需要used数组记录path里都放了哪些元素了。然后当path路径的大小和used数组一样大的时候，说明path路径里面包含了used数组里面所有的元素，就可以终止了。
47.全排列 II
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容： used[i - 1] == true 也行，used[i - 1] == false 也行
代码随想录
视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili
class Solution {private List<Integer> path = new ArrayList<>();private List<List<Integer>> result = new ArrayList<>();private int[] used; public List<List<Integer>> permuteUnique(int[] nums) {used = new int[nums.length];Arrays.sort(nums);permuteUniqueHelper(nums);return result; }public void permuteUniqueHelper(int[] nums){if(path.size() == nums.length){result.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){if(i > 0 && used[i-1] == 0 && nums[i] == nums[i - 1]){continue;} //树层去重if(used[i] == 1){continue;}path.add(nums[i]);used[i] = 1;permuteUniqueHelper(nums);used[i] = 0;path.remove(path.size() - 1);}}
}总结
1.这道题就是在上一道题的基础上加上对树层去重的操作。树层去重也可以刚好使用到used数组。
2.排列问题的去重其实对树层去重和对树枝去重都是可以的。因为排列问题每一层遍历的集合都是全部遍历，是相同的。纵向去重相当于把横向数组转了90度。只是去重的过程中我们要坚持一个原则，要么是对树层去重，要么是对树枝去重。对树层去重的效率更高，只要掌握对树层去重就可以了，避免搞混了。
下面这三道题都非常难，建议大家一刷的时候 可以适当选择跳过。
因为 一刷 也不求大家能把这么难的问题解决，大家目前能了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。
332.重新安排行程（可跳过）
本题很难，一刷的录友刷起来 比较费力，可以留给二刷的时候再去解决。
本题没有录制视频，当初录视频是按照 《代码随想录》出版的目录来的，当时没有这道题所以就没有录制。
代码随想录
51.N皇后（适当跳过）
N皇后这道题目还是很经典的，一刷的录友们建议看看视频了解了解大体思路 就可以 （如果没时间本次就直接跳过） ，先有个印象，二刷的时候重点解决。
代码随想录
视频讲解：这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后_哔哩哔哩_bilibili
class Solution {//private List<String> path = new ArrayList<>();//把每一行的结果理解为path路径上面的一个节点private List<List<String>> result = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for(char[] row : chessboard){Arrays.fill(row, '.');}solveNQueensHelper(0, n, chessboard);return result; }public void solveNQueensHelper(int row, int n, char[][] chessboard){if(row == n){result.add(ArrayToList(chessboard));}for(int i = 0; i < n ; i++){if(!isValid(chessboard, row, i, n)){continue;}chessboard[row][i] = 'Q';solveNQueensHelper(row+1, n, chessboard);chessboard[row][i] = '.';}}public List<String> ArrayToList(char[][] chessboard){List<String> path = new ArrayList<>();for(char[] row : chessboard){path.add(new String(row));}return path;}public boolean isValid(char[][] chessboard, int row, int col, int n){//需要明确的一个原则是只对已经添加了元素的行判断是否合法for(int i = 0; i < row; i++){if(chessboard[i][col] == 'Q'){return false;}}//检查对角线的元素，只要检查已经添加好元素的行，没有添加元素的行不用管，并不是对所有的对角线元素进行考虑for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--,j--){if(chessboard[i][j] == 'Q'){return false;}}for(int i = row-1, j = col+1; i >= 0 && j < n; i--, j++){if(chessboard[i][j] == 'Q'){return false;}}return true;}}总结
1.这道题的大体思路和回溯算法是一致的。只不过我们这次for循环针对的集合是二维棋盘的每一行，每次for循环对棋盘的一行进行处理。然后我们只需要判断元素是否合法，如果合法就加入到棋盘里面。如果棋盘可以遍历到叶子节点，也就是可以遍历到棋盘的最后一行，说明这个结果是可以保存下来的。
2.写这道题必须明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。
3.然后就是两个工具函数的实现。public List<String> ArrayToList(char[][] chessboard)这个函数可以把一个二维棋盘转为List<String>，只需要对每一行for循环，然后new String(char[])，就可以把一个以为的数组转为String，然后对每一行都同样处理加入到List<String>里面。
4.public void solveNQueensHelper(int row, int n, char[][] chessboard)这个函数是判断在一个 n×n 的国际象棋棋盘 chessboard 上，尝试将皇后放置在 (row, col) 位置时，是否符合国际象棋规则。它确保没有其他皇后可以威胁到该位置。首先是判断列上面有么有冲突(行上面不会有冲突，因为每次递归都会进入到不同行)，然后是45度和135度的对角线上面。需要明确的一个原则是只对已经添加了元素的行判断是否合法，没有添加元素的行不用管，并不是对所有行的对角线元素进行考虑。
37.解数独（适当跳过）
同样，一刷的录友们建议看看视频了解了解大体思路（如果没时间本次就直接跳过），先有个印象，二刷的时候重点解决。
代码随想录
视频讲解：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili
总结
1.这道题为什么需要使用两层for循环呢？
N 皇后和数独的本质差异
在N 皇后问题中：
- 每行必须且只能放置一个皇后，因此递归自然控制行的递进。
- 列的选择是有限的：每一行中只需要决定一个列位置（一个解法对应一个皇后放置方案）。
- 不会有空位问题，递归中没有跳过特定列的需求。
在数独问题中：
- 棋盘中的空位是稀疏且分布不均的。可能某行有多个空格，某行没有空格。
- 数独的目标是填满所有空格，而不是一行仅填一个数字。
- 因此，你无法只通过单层列循环处理棋盘，递归也无法单独处理行推进。
可以理解N 皇后问题当中，每次for循环，在一行填充了一个元素之后，相当于本行就处理完了，可以递归到下一行进行处理。但在数独问题当中，在一行填充了一个元素之后，我们需要继续去填充后面的元素。所以我们必须处理完当前行的逻辑才能进行下一层的递归，这时候就要一个for循环来帮我们进行列的遍历。在填充了一个元素之后，列的for循环帮我们移动到下一个元素。
2.数独的核心在于逐个处理空格，按照从上到下、从左到右的顺序填充空格。行递归会限制灵活性，因为它是以整行的方式进行，而不是以具体空格的方式。
3.当前实现通过双层循环准确定位到空格 (i, j)，可以直接判断当前空格是否可以放入某个数字，发现不行时立即跳过。如果使用行递归，则需要额外处理如何跳过已经预填充的位置和无效的递归路径，逻辑复杂且容易遗漏。
4.就把这道题的两层for循环当作对数组里面每一个元素的遍历，如果是空格，然后我们往空格里面一个个添加1-9,然后递归和回溯帮我们一个个的尝试这些组合，并返回true和false。递归和回溯的作用就是帮我们尝试，然后撤销，也起到判断的作用。
总结
刷了这么多回溯算法的题目，可以做一做总结了！
代码随想录