跳至主要內容

skill-08-回溯算法

holic-x...大约 70 分钟算法算法

难度说明：🟢简单🟡中等🔴困难

学习资料

学习目标

  • 掌握数据结构核心基础
  • 借助数据结构完成常见题型

skill-08-回溯算法

理论基础

1.核心理论

（1）回溯算法题型分类

  • 组合（N个数里面按一定规则找出k个数的集合）组合无序（组合不强调排列顺序）
    • 077-组合
    • 017-电话号码和字母组合
    • 039-组合总和
    • 040-组合总和II
    • 216-组合总和III
  • 分割（一个字符串按一定规则有几种切割方式）
    • 131-分割回文串
    • 093-复原IP地址
  • 子集（一个N个数的集合里有多少符合条件的子集）
    • 078-子集（给定非重复数组）
    • 090-子集II（给定可能存在重复元素的数组）
    • 491-非递减子序列
  • 排列（N个数按一定规则全排列，有几种排列方式）排列有序（排列强调元素顺序）
    • 046-全排列（给定非重复数组）
    • 047-全排列II（给定可能存在重复元素的数组）
  • 棋盘问题
    • 051-N皇后
    • 037-解数独
  • 其他
    • 491-递增子序列（和子集问题类似）
    • 332-重新安排行程

回溯相关场景分析

  • 组合（N个数里面按一定规则找出k个数的集合）组合无序（组合不强调排列顺序）
    • 077-组合（返回范围 [1, n] 中所有可能的 k 个数的组合，不限定顺序、每个元素只能用1次）
    • 017-电话号码和字母组合
      • 回溯法（字母映射，然后对每个数字对照的字符序列匹配回溯处理）
      • 队列法（基于遍历的思路，借助队列辅助遍历，每次取出当前队列中的序列拼接，当所有的数字遍历处理完成，最终队列中留存的序列即为所得）
    • 039-组合总和（找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，不限定顺序，同一个数可以使用多次）
      • 回溯法（基础版本，注意递归出口curPathSum>=target和idx参数（可重复））
      • 回溯法-剪枝优化（排序 + 剪枝，优化回溯效率）
    • 040-组合总和II（找出 candidates 中所有可以使数字和为 target 的组合。不限定顺序，同一个数字只能使用1次）
      • 回溯法：基于回溯模板构建，注意递归出口、去重处理
      • 回溯法-剪枝优化：（排序 + 剪枝（排序后连续重复的选择则跳过），优化回溯效率）
    • 216-组合总和III（返回范围 [1, 9] 中相加和为n的 k 个数的组合，不限定顺序、每个元素只能用1次）
  • 分割（一个字符串按一定规则有几种切割方式）
    • 131-分割回文串（将字符串s分割为多个子串，使得每个子串都为回文串）
      • 回溯法：检验当前分割位置，如果当前分割位置的字符串为回文串，则可以递归处理每个分割位置，否则跳过
    • 093-复原IP地址
      • 思路与【131】类似，此处需注意截断字符串校验
  • 子集（一个N个数的集合里有多少符合条件的子集）
    • 078-子集（给定非重复数组）
      • 回溯法：递归回溯处理，每次选择一个数，结果集的记录无条件限制，递归出口实际为遍历到数组末尾就结束（for中已限定，可以不用额外指定递归出口）
    • 090-子集II（给定可能存在重复元素的数组）
      • 排序+回溯法：和【078】类似，此处需要处理重复元素，因此需要进行排序并进行去重校验（可以排序后contains校验，也可以在for循环中判断是否出现连续重复的情况，出现则跳过）
    • 491-非递减子序列
      • 回溯法：和子集问题类似，此处需要注意结果集处理和剪枝处理
        • ① 结果集处理：满足条件则加载结果集（此处递归出口可以由for循环控制）
        • ② 剪枝：判断是否满足递增条件（路径的最后一个元素与当前遍历元素比较）、去重处理（Set处理）
  • 排列（N个数按一定规则全排列，有几种排列方式）排列有序（排列强调元素顺序）
    • 046-全排列（给定非重复数组）
      • 回溯 + 交换：参考子集问题解决思路，此处主要有两点不同
        • ① 递归出口是载入叶子节点的完整路径
        • ② 递归回溯处理过程是交换元素后进行递归处理，处理完成后复原现
      • 回溯 + 全排列思路：每一层从下标0位置开始选择一个元素（如果当前路径curPath已经选了则跳过，当当前路径的长度和数组长度一致说明构成了一个排列顺序）
    • 047-全排列II（给定可能存在重复元素的数组）
      • 回溯 + 交换 + 排序去重：和【046】思路类似，但是此处需注意去重处理
  • 棋盘问题
    • 051-N皇后
      • void backTrack(int row,int n,char[][] board) row 为指定行，回溯处理选择填充列：校验当前择定位置是否满足放置条件，满足则进一步递归，不满足则跳过
    • 037-解数独
      • boolean backTrack(char[][] board) 为九宫格中的每一个尚未填充的元素位置从[1,9]中选择一个数字校验是否满足填充条件，满足则进一步递归处理下一个位置，不满足则跳过
  • 其他
    • 491-递增子序列（和子集问题类似）
    • 332-重新安排行程

（2）回溯法

​ 回溯法也称为回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。回溯并不算什么高效的算法，其本质是穷举所有可能，然后选出所需要的答案。可以增加一些剪枝的操作优化复杂度，但是也改变不了回溯法穷举的本质。

​ 既然回溯法并不高效，那为什么还要用？ 对比一些问题的传统暴力搜索方式，回溯法可以通过剪枝的方式优化复杂度，相对而言更加高效

回溯法应用场景和技巧理解

​ 回溯法可以解决的问题，可以结合题目分类理解，一般是组合、切割、子集、排列、棋盘问题等，回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）

回溯模板

  • 【1】回溯函数backTrack返回值及参数

    • 一般回溯算法没有返回值，回溯的核心是全局参数复原概念

      public void backTrack(参数){ }

  • 【2】回溯函数终止条件（参考递归，遍历树形结构需要有终止条件，因此回溯也要设定终止条件）

    • 什么时候到达终止条件，一般来说搜索到叶子节点（或者一些特殊场景条件下的终止）

      • 结果收集问题：注意此处的结果收集，不一定是要放在终止条件，此处的概念更倾向是如果遇到满足条件的情况需要进行结果收集并退出递归（例如全子集问题收集所有结果，因此它不需要限制结果收集的条件），但也要注意其他的一些终止条件限制（剪枝）
      # 版本1
if(终止条件){
    // todo 存放结果（此处是有条件的收集结果，如果不需要限制条件收集结果则放在外层）
	return;
}

# 版本2
// 剪枝（递归出口）
if(终止条件){
	return;
}
// 结果收集（递归出口）
if(终止条件){
    // todo 存放结果（此处是有条件的收集结果，如果不需要限制条件收集结果则放在外层）
	return;
}

  • 【3】回溯搜索的遍历过程

    • 回溯一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度
    image-20241118091632735
// 回溯过程伪代码
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    1.处理节点; // 尝试
    2.backTrack(路径，选择列表); // 递归
    3.回溯，撤销处理结果 // 复原现场
}

回溯的过程涉及到两个循环，一个是横向循环，一个是纵向循环，基于此将整棵树遍历完

  • 横向循环：for 循环遍历集合区间（一个节点有多少个有多少个孩子，这个 for 循环就执行多少次）
  • 纵向循环：backTrack 递归调用

基于上述分析，最终得到回溯算法模板：

public void backTrack(参数){ 
    // 终止条件
    if(终止条件){
        // todo 存放结果
        return;
    }

    // 回溯过程
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        1.处理节点; // 尝试
        2.backTrack(路径，选择列表); // 递归
        3.回溯，撤销处理结果 // 复原现场
    }
}

2.技巧总结

组合问题

​ 对于组合问题，什么时候需要startIndex什么时候不需要？取决于遍历的是一个集合还是多个集合

  • 如果是一个集合求组合，需要使用startIndex（例如【77-组合】、【216-组合总和III】）
    • 组合元素的重复问题：在一些组合场景中，如果希望得到的组合元素不重复，那么在递归的时候限定从当前遍历位置的下一位（i+1）进行迭代，以此避免组合加入重复的元素；如果允许组合元素重复，则递归传入的是i
  • 如果是多个集合去取组合，多个集合之间不受影响（例如【17-电话号码的字母组合】）

结果收集（递归出口分析）

​ startIndex的递归出口校验，对于回溯的组合、子集、全排列问题，一般用startIndex来限定集合的遍历范围，因此一些情况下也用startIndex的取值来校验递归出口，但实际上校验startIndex是否到达集合尾部并不是必选项，因为在回溯过程中（for循环）中已经对startIndex的取值做了限制，可以不用在递归出口中进行重复校验，反而关注的是限定条件下结果集的收集（将其作为递归出口）

  • 组合问题：满足收集到指定个数或者指定元素和的path则进行收集
    • 此外，针对【可以重复使用同一个元素】的组合场景，由于无法判断递归的深度（由于元素可以重复使用，则递归深度不可简单通过长度或者startIndex进行限制），因此需要通过限定条件进行剪枝
      • 例如元素均为正整数，收集元素和为target的组合场景（允许重复使用同一个元素），则可通过curPathSum>target进行剪枝（当前路径元素和已经大于target，再继续添加其他正数只会比target更大，直接剪枝（即递归结束））
  • 子集问题：收集每个节点的路径集合（区分nums是否存在重复元素的情况，作去重处理）
    • ① nums 不存在重复元素，直接收集（每个节点都要收集路径）
    • ② nums 存在重复元素，直接收集，还需进行去重处理（在nums（排序）的基础上进行校验）需排序
      • 思路1（结果集校验）：!res.contains(new ArrayList<>(path))情况下才载入结果集
      • 思路2（递归前剪枝）：需在回溯过程中进行剪枝后递归（校验排序后的数组是否在同一层的选择中选中同一个元素）if (i > idx && nums[i - 1] == nums[i]) { continue; // 出现连续重复，跳过当前分支（相当于同一层选到同一个元素） }
  • 全排列问题：
    • ① nums 不存在重复元素，到达叶子节点才进行收集（即path长度为nums长度或者startIndex到达nums末尾）
      • 思路1（递归交换）：基于startIndex处理，递归交换i与startIndex位置并记录结果
      • 思路2（哈希表，全排列思路）：取消startIndex概念，for中的选择列表是[0,n-1]中还没取过的元素（即path中还没出现过的元素，因为元素中不存在重复元素，所以可以用path来判重，或者定义哈希表来判重）即可
    • ② nums 存在重复元素，到达叶子节点收集结果，且需进行去重处理 不需排序（对于全排列问题，顺序影响结果，不同的排列顺序代表不同的结果，因此去重处理过程中不能进行排序处理）
      • 思路1（递归交换）：基于startIndex处理，递归交换i与startIndex位置并记录结果，且用set记录已经出现过的元素进行剪枝处理
      • 思路2（哈希表，全排列思路）：取消startIndex概念，for中的选择列表是[0,n-1]中还没取过的元素（因为元素中存在重复元素，因此需用boolean[]标识元素是否已经被取过），且需在递归前进行去重判断

​

  • 组合问题、分割问题：收集树形结构中限定条件的路径遍历结果（满足限定条件）

    public void backTrack(int[] nums, int startIndex) {
    // 递归出口
    if(递归出口条件){ // 例如k个元素组合（那么此处的递归出口就是curPath.size()==K）
        if(....限定条件载入结果集){ // 可能还会限定条件
            // 将路径载入结果集
        	res.add(new ArrayList<>(curPath));
        }
    	return;
    }
    
    // 回溯过程
    for (int i = startIndex; i < nums.length; i++) {
        ......
    }
}

  • 子集：收集树形结构中树的所有节点的结果

    public void backTrack(int[] nums, int startIndex) {
    // 将路径载入结果集
    res.add(new ArrayList<>(curPath));

    // 递归出口（此处也可以不指定，因为当满足这个条件时for循环也遍历结束了）
    if(startIndex>=nums.length){
    	return;
    }
    
    // 回溯过程
    for (int i = startIndex; i < nums.length; i++) {
        ......
    }
}

  • 全排列：收集树形结构中叶子节点的结果

    public void backTrack(int[] nums) {
    // 递归出口
    if(curPath.size==nums.length){ // 全排列序列的长度和数组元素长度是一致的
        // 将路径载入结果集
   		res.add(new ArrayList<>(curPath));
    	return;
    }
    
    // 回溯过程
    for (int i = 0; i < nums.length; i++) { // 全排列是具备顺序性的，因此每次都是从头开始搜索
        ......
    }
}

【子集、全排列】的集合去重问题

对于这类问题的求解，先按照思路将【不重复的数组元素集合】这个方案模板敲定下来，然后再思考如何进行剪枝去重，思路会更加清晰

​ 此处的集合去重（注意此处要解决的是集合重复问题（[1,2,2]是允许的），而不是集合中的元素重复问题）问题，以子集为例有两种求解子集的题型，一种是给定不重复的数组元素集合，一种是给定可能存在重复元素的数组元素集合

  • 对于【不重复的数组元素集合】，只要确保每次选择节点的时候不选已经选过的元素即可（即设定startIndex，递归时选择从i+1位置开始递归）

  • 对于【可能存在重复元素的数组元素集合】，还要考虑排除掉当层重复的元素，此处有两种方向的解决思路：

    • （1）硬核思路：正常处理集合，在载入结果集的时候进行去重判断（交由去重方法处理）

    • （2）回溯处理去重问题：在回溯的过程中进行去重判断（可以理解为剪枝），此处又可以扩展多个思路

      • 思路1：先排序，后同一层相邻元素比较是否相等（存在相等则说明重复，需剪枝）

        Arrays.sort(nums); // 在回溯方法调用之前对整体数组nums进行排序

// for 循环递归的时候处理
for(...){
    // 去重处理（剪枝）
    if(i>startIndex && nums[i-1]==nums[i]){
		continue;
	}
}

      • 思路2：先排序，set 校验（判断set集合是否已经使用过某个元素，如果是则剪枝，每次回溯遍历节点的过程都将已遍历的节点加入set）

        • 此处先排序后校验主要在于子集中不强制顺序，因此要把顺序固定下来，集合去重才有意义（否则[1 2]、[2 1]这种情况无法排除）；针对全排列其本身就限定了顺序，认为[1 2]、[2 1]是两个不同的排列顺序结果集，因此直接进行判断即可（不需要单独额外排序）
        // 回溯算法
public void backTrack(int[] nums, int startIndex) {
    // 将路径载入结果集(在回溯过程中进行了去重处理，此处直接载入子集到结果集即可)
    res.add(new ArrayList<>(curPath));
    
    // set 做去重判断
    HashSet<Integer> hs = new HashSet<>();

    // 回溯过程
    for (int i = startIndex; i < nums.length; i++) {
        // 剪枝：去除重复集合的情况，避免同一层取到同样元素
        if (!hs.isEmpty() && hs.contains(nums[i])) {
            continue;
        }

        hs.add(nums[i]); // 记录已遍历节点

        // 处理节点
        curPath.add(nums[i]);
        // 递归
        backTrack(nums, i + 1);
        // 回退,复原现场
        curPath.remove(curPath.size() - 1);
    }
}

      • 补充说明：注意这个场景中要解决的是集合重复问题（[1,2,2]是允许的），而不是集合中的元素重复问题。所以对于子集而言不能单纯通过curPath.contains(nums[i])进行判断

时间复杂度分析

一般回溯算法的复杂度，都说是指数级别的时间复杂度

子集问题分析：

  • 时间复杂度：$O(n × 2n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$
  • 空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$

排列问题分析：

  • 时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。
  • 空间复杂度：$O(n)$，和子集问题同理

组合问题分析：（可以理解为子集的特例）

  • 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度
  • 空间复杂度：$O(n)$，和子集问题同理

常见题型

🍚01-组合问题

🟡组合（077）

1.题目内容open in new window

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]
2.题解思路
👻方法1：暴力循环搜索（❌）
  • 思路分析：通过构建K层嵌套循环实现暴力搜索
    • 如果k==2则找两个数的组合，可以通过构建2层循环暴力检索；以此类推，如果k==3那么可以构建3层循环暴力检索；但随着层数的堆积，这种暴力检索的方式无疑是灾难性的设计
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        for(int m=j+1;m<=n;m++){
            ......
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

👻方法2：回溯法（🚀）

  • 思路分析：将题意转化为树结构，然后按照回溯模板的定义进行设计

    • 树结构分析

      image-20241118100500918

    • 回溯方法（返回类型、参数）

      • 返回类型为void
      • 参数：
        • 基础形式参数：n、k（遍历n个元素、限定k个数的组合），通过cur记录当前遍历的位置（因为限定不能重复使用元素，因此要用cur来记录当前遍历位置，每次递归都是从cur+1的位置开始进而过掉已经遍历过的元素）
        • 全局参数：res 全局结果集、curPath 当前遍历路径（也可将其放入递归函数的参数中进行处理，但为了代码可读性此处将其提取出来作为全局变量）

    • 回溯出口

      • 什么时候更新结果集？=》当curPath集合大小有K个元素的时候说明这个时候凑够了K个数的组合，此时可以将curPath加入结果集

    • 回溯过程：每次从集合中选取元素，可选择的范围随着选择的进行而收缩（调整可选择的范围）

      • 处理当前节点：将当前节点加入路径
      • 两个循环：横向for、纵向递归
        • for：从cur出发、到n结束
        • 递归： 递归cur+1（此处的cur+1可以理解为缩圈，限定下一个递归可访问的开始起点，理解为startIndex可能更为准确）
      • 复原现场
/**
 * 077 组合
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义全局结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前遍历路径的结果集

    public List<List<Integer>> combine(int n, int k) {
        // 调用回溯算法
        backTrack(n, k, 1); // 起始从1开始
        // 返回结果
        return res;
    }


    /**
     * 定义回溯算法
     *
     * @param n          n 个 元素
     * @param k          k 个 数 (k个数构成一个组合)
     * @param startIndex 当前遍历的元素起点位置（cur理解为startIndex更为准确）
     */
    public void backTrack(int n, int k, int startIndex) {
        // 递归出口:当当前节点路径节点个数满足k个则录入结果集
        if (curPath.size() == k) {
            // 处理结果（将当前路径加入到结果集）
            res.add(new ArrayList<>(curPath)); // 构建结果集需要new一个对象，避免引用影响
            return;
        }

        // 回溯过程
        // for (int i = cur; i <= n; i++) { // 起始从1开始：[1,n]
        for (int i = startIndex; i <= n - (k - curPath.size()) + 1; i++) { // 剪枝优化：只要确保startIdx的位置要满足可以构成k个元素的组合
            curPath.add(i);
            backTrack(n, k, i + 1); // 递归
            curPath.remove(curPath.size() - 1); // 复原现场
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

回溯算法的剪枝优化

​ 分析回溯算法的for循环条件：for(int i=cur;i<n;i++)，如果for循环从起始节点开始之后的元素个数已经不满足k个，则根本不可能构成k个数的组合，因此此处可以进行剪枝优化：

  • 剪枝优化分析
    • 已经选择的元素个数：xcurPath.size()
    • 还需要的元素个数：y k-curPath.size()
    • 因此遍历元素的起点至少应为：n-y+1即n-(k-curPath.size())+1（左闭），只有从这个节点及之前开始遍历，才可能构成k个数的组合
  • 案例分析：假设[1,2,3,4](n=4,k=3)，则一开始遍历元素的起点至少为2开始才可能构成3个数的组合（而对于递归过程来说则还需去掉已经选择的元素个数）
  • 基于此进一步优化for条件：for(int i=cur;i<n-(k-curPath.size())+1;i++)

🟢组合总和III（216）

1.题目内容open in new window

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
2.题解思路
👻方法1：回溯法
  • 思路分析：此处基于回溯法的思路进行构建（和【077-组合】解题思路类似），只是此处还要同步维护路径和（curPathSum）用于校验
/**
 * 216 组合总和 III
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 定义当前路径节点之和（和curPath相匹配）

    public List<List<Integer>> combinationSum3(int k, int n) {
        // 调用回溯函数
        backTrack(k, n, 1);
        // 返回结果
        return res;
    }

    // 定义回溯函数
    public void backTrack(int k, int n, int startIdx) {
        // 回溯出口：curPath中k个节点累加和为n
        if (curPath.size() == k && curPathSum == n) {
            // 处理结果
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 回溯过程
        for (int i = startIdx; i <= 9; i++) { // 只能使用[1,9]的数字
            // 1.处理节点
            curPath.add(i);
            curPathSum += i;
            // 2.递归
            backTrack(k, n, i + 1); // 注意此处递归是取当前遍历元素的下一个（i+1）
            // 3.复原现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= i;
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

剪枝优化分析：

​ 同理，针对回溯算法进行剪枝优化分析，和【077-组合】这题类似，此处要对for循环的取值范围进行剪枝优化

  • for循环剪枝优化：
    • 【剪枝思路1】k个数的组合：i的取值范围[startIdx,9]=》[startIdx,9-(k-curPath.size())+1]
    • 【剪枝思路2】路径和校验：如果在当前遍历周期 处理回溯过程之前就发现curPathSum>targetSum则说明后续递归的结果肯定也不满足，因此直接砍掉这个分支
/**
 * 216 组合总和 III
 */
public class Solution2 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 定义当前路径节点之和（和curPath相匹配）

    public List<List<Integer>> combinationSum3(int k, int n) {
        // 调用回溯函数
        backTrack(k, n, 1);
        // 返回结果
        return res;
    }

    // 定义回溯函数
    public void backTrack(int k, int n, int startIdx) {
        // 回溯出口：curPath中k个节点累加和为n
        if (curPath.size() == k && curPathSum == n) {
            // 处理结果
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 回溯过程
        // 剪枝优化1：k个元素组合（限定i的最大取值为`9-(k-curPath.size())+1`）
        for (int i = startIdx; i <= 9-(k-curPath.size())+1; i++) { // 只能使用[1,9]的数字，限定i取值范围[startIdx,9-(k-curPath.size())+1]
            // 剪枝优化2：如果当前遍历周期的curPathSum>n已经满足，则后续递归的结果只会更大（因为此处是累加正数），直接剪枝
            if(curPathSum>n){
                break; // 剪枝
            }

            // 1.处理节点
            curPath.add(i);
            curPathSum += i;
            // 2.递归
            backTrack(k, n, i + 1); // 注意此处递归是取当前遍历元素的下一个（i+1）
            // 3.复原现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= i;
        }
    }
}

image-20241118115616444

🟡电话号码和字母的组合（017）

1.题目内容open in new window

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

// 定义数字和字母映射集合
Map<Integer, String> map = new HashMap<Integer, String>() {{
    put(2, "abc");
    put(3, "def");
    put(4, "ghi");
    put(5, "jkl");
    put(6, "mno");
    put(7, "pqrs");
    put(8, "tuv");
    put(9, "wxyz");
}};

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]
2.题解思路
👻方法1：回溯法
  • 思路分析：中规中矩按照回溯法模板定义整体算法的基本框架，此处的重点核心关注，不再纯粹是数字的组合，而是循环遍历数字的过程需要将数字对应的字符进行处理
    • 即此处如果按照回溯模板来分析，for循环遍历的应该是指定数字对应的字母集合，回溯的过程是将这些字母集合内容都拼一遍、回溯，构成路径。其核心在于在原有的数字组合的基础上内嵌一层数字对应的字母集合的遍历（而真正的递归回溯是针对当前遍历数字对应的字母集合来执行的）
    • ==注意：==注意字符串的字符和数字的比较，默认比较的是ASCII值，因此此处要手动转化，或者定义map集合的时候将映射集合定义为Map<Character, String>
image-20241118133356738
/**
 * 017 电话号码和字母的组合
 */
public class Solution1 {

    List<String> res = new ArrayList<>(); // 定义结果集
    StringBuffer curPath = new StringBuffer(); // 定义当前遍历路径

    // 定义数字和字母映射集合
    Map<Character, String> map = new HashMap<Character, String>() {{
        put('2', "abc"); // 注意字符和数字的比较转换，此处用字符处理
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        // digits 为空判断
        if (digits == null || "".equals(digits)) {
            return new ArrayList<>();
        }

        // 调用回溯方法
        backTrack(digits, 0);
        // 返回结果
        return res;
    }


    /**
     * 回溯法
     *
     * @param digits 遍历字符串
     * @param cur    当前遍历位置
     */
    public void backTrack(String digits, int cur) {
        // 回溯出口：当curPath长度和digits长度一致(或者cur遍历到字符串末尾)
        if (curPath.length() == digits.length()) {
            // 处理结果：将当前路径加入结果集
            res.add(new StringBuffer(curPath).toString());
        }

        // 回溯过程
        for (int i = cur; i < digits.length(); i++) {
            // 根据当前遍历指向数字，循环处理相应的字符
            String curChars = map.get(digits.charAt(i));
            for (int j = 0; j < curChars.length(); j++) { // 此处是根据数字指向的字符序列映射进行处理，因此需嵌套循环处理每个匹配的字符
                // 1.处理节点
                curPath.append(curChars.charAt(j));
                // 2.递归
                backTrack(digits, i + 1); // 递归下一个元素
                // 3.恢复现场
                curPath.deleteCharAt(curPath.length() - 1); // 删除最后一个元素
            }
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

👻方法2：迭代法（基于队列辅助遍历）
  • 思路分析：基于层次遍历的思路进行迭代，借助辅助队列实现
    • 案例分析：以"23"为例，构建辅助队列做处理（初始化进入""空字符串），循环遍历目标字符串的数字，然后取出当前队列元素进行拼接后入队更新，循环往复
      • 遍历到"2"，取出""，拼接成a、b、c然后重新放入队列
      • 遍历到"3"，取出a、b、c，拼接成ad、ae、af、bd、be、bf、cd、ce、cf然后重新入队（需注意每次取出的元素为当层遍历的元素个数，在后续迭代过程中queueSize会变化，因此先记录要当层要取出的元素个数）
      • 遍历完成（digit所有数字遍历完毕），取出当前队列所有元素即为所得
/**
 * 017 电话号码和字母的组合
 */
public class Solution2 {

    // 定义数字和字母映射集合
    Map<Character, String> map = new HashMap<Character, String>() {{
        put('2', "abc"); // 注意字符和数字的比较转换，此处用字符处理
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        // digits 为空判断
        if (digits == null || "".equals(digits)) {
            return new ArrayList<>();
        }

        // 构建辅助队列
        Deque<String> queue = new LinkedList<>();
        queue.offer("");

        // 迭代法
        for (int i = 0; i < digits.length(); i++) {
            //  记录当层元素个数，取出队列元素，根据当前遍历字符串指向数字进行拼接，随后更新入队
            int curSize = queue.size();
            for (int j = 0; j < curSize; j++) {
                // 取出队列中当层元素进行拼接
                String curPath = queue.poll();
                String charMap = map.get(digits.charAt(i));
                // 处理新字符
                for (int k = 0; k < charMap.length(); k++) {
                    queue.offer(curPath + charMap.charAt(k)); // 拼接新元素，入队
                }
            }
        }

        // 目标字符串遍历完成，取出目前队列元素
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            res.add(queue.poll());
        }

        // 返回结果
        return res;
    }
}

  • 复杂度分析

    • 时间复杂度：O（n × m） n 为digits字符串的数字个数，m为对应每个数字映射的字符个数（可能并不是每个数字都对应同样的字符个数）

    • 空间复杂度：O（m）基于队列辅助遍历，此处队列占用最大长度取决于数字对应字符的最长长度（通过画图可知）

🟡组合总和（039）

1.题目内容open in new window

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []
2.题解思路
image-20241118143925914
👻方法1：回溯法
  • 思路分析：将题意转化为树
    • 题意分析：此处对比前面的组合问题主要有两点的不同：
      • （1）组合没有数量要求（因此无法界定递归层数，需自行确定递归出口）
      • （2）元素可以无限重复选取（因此不能单纯通过遍历到叶子节点就判断为出口，而是要通过剪枝处理）
    • 递归出口：从图示可以看到，由于每次可以取重复的元素，因此树的层数是无法固定的，因此递归的出口是sum>=target（等于的情况是找到满足条件的的路径需处理结果并退出递归，大于的情况是继续递归下去累加正数更加不可能得到target，因此在没有限定递归层数的情况下通过这个条件剪枝，否则就会出现StackOverFlow栈溢出）
/**
 * 039 组合总和
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 定义当前路径和(与当前路径同步匹配)

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 调用回溯算法
        backTrack(candidates, target, 0);
        // 返回结果
        return res;
    }


    // 回溯算法
    public void backTrack(int[] nums, int target, int idx) {
        // 回溯出口：如果找到路径和为目标target则记录结果集,或者递归到当前累加和大于target直接剪枝（递归退出）
        if (curPathSum == target) {
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 由于无法固定递归层数，此处需要进行剪枝 如果sum大于target则无需继续递归（剪枝）
        if (curPathSum > target) {
            return;
        }

        // 回溯过程
        for (int i = idx; i < nums.length; i++) {
            // 1.处理节点
            curPath.add(nums[i]);
            curPathSum += nums[i];
            // 2.递归
            backTrack(nums, target, i); // 元素允许重复，此处可以从i开始继续递归
            // 3.恢复现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= nums[i];
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

剪枝优化（排序+剪枝）

​ 【剪枝优化方向】排序后再求组合和，可以根据当前遍历路径和与target比较进行剪枝，参考此前的组合题解，在数组有序的场景下或者数组中全为正数的情况下，路径遍历则相应累加和也会不断变大，因此可以基于这个情况，在循环遍历的时候进入节点之前先进行剪枝

image-20241118151046547
/**
 * 039 组合总和
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 定义当前路径和(与当前路径同步匹配)

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 排序
        Arrays.sort(candidates);
        // 调用回溯算法
        backTrack(candidates, target, 0);
        // 返回结果
        return res;
    }


    // 回溯算法
    public void backTrack(int[] nums, int target, int idx) {
        // 回溯出口：如果找到路径和为目标target则记录结果集,或者递归到当前累加和大于target直接剪枝（递归退出）
        if (curPathSum == target) {
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 由于无法固定递归层数，此处需要进行剪枝 如果sum大于target则无需继续递归（剪枝）
//        if (curPathSum > target) {
//            return;
//        }

        // 回溯过程
        for (int i = idx; i < nums.length; i++) {
            // nums为排序后的数组，因此此处可以进行剪枝判断
            if(curPathSum+nums[i]>target){
                break; // 如果当前这个路径和遍历元素的累加和大于target，则后续的节点累加和更加不可能构成target，直接跳出
            }

            // 1.处理节点
            curPath.add(nums[i]);
            curPathSum += nums[i];
            // 2.递归
            backTrack(nums, target, i); // 元素允许重复，此处可以从i开始继续递归
            // 3.恢复现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= nums[i];
        }
    }
}

🟡组合总和II（040）

1.题目内容open in new window

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
2.题解思路
👻方法1：回溯法
  • 思路分析：按照回溯模板进行构建
    • 递归出口：此处和【039-组合总和】不同点在于，其递归层数是可确定的，因为限定元素不能重复使用（即原数组中的每个元素只能使用一次），且构建的组合不能重复
      • 基于题意可以得到递归出口是 startIndex 遍历到数组尾部（深度是确定的） 或者 找到目标target的路径 （当然也可以是参考【039-组合总和】的剪枝判断curPathSum>target时直接砍掉）
    • 递归过程：递归过程是遍历数组元素，然后处理节点、递归（递归需从i+1位置开始）、复原
      • 为什么要先对目标数组进行排序：此处排序有两点好处，一来是方便剪枝、二来是便于去重判断
// ❌❌❌❌❌ 超时 ❌❌❌❌❌
/**
 * 040 组合总和II
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 同步记录当前路径和

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        // 调用回溯方法
        backTrack(candidates, target, 0);
        // 返回结果
        return res;
    }


    // 回溯算法
    public void backTrack(int[] nums, int target, int startIndex) {
        // 递归出口：遍历到集合末尾或者找到目标target
        /*
        if (startIndex > nums.length) { // 元素不允许重复，则说明遍历到数组末尾即结束(此处的递归出口可由for控制，无需校验，可省略)
            return;
        }
        */

        if (curPathSum == target) {
            // 处理结果(需判断重复组合)
            if(!res.contains(new ArrayList<>(curPath))){
                res.add(new ArrayList<>(curPath)); // 将当前路径加入结果集（需new一个对象，避免引用影响）
            }
            return;
        }

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            // 1.处理节点
            curPath.add(nums[i]);
            curPathSum += nums[i];
            // 2.递归
            backTrack(nums, target, i + 1); // 不允许组合元素重复使用，此处从当前遍历节点位置的下一位开始
            // 3.复原现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= nums[i];
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

优化版本：上述的内容会执行超时

​ 主要在于去重判断的处理会导致结果超时，因此基于优化复杂度的考虑，要进行剪枝优化、去重优化处理

  • 对数组进行排序，便于剪枝优化

  • 递归出口：

    • 原startIndex == nums.length是最坏的打算，这种情况下认为遍历到叶子节点递归结束（最原始的出口判断，此处递归层数限定最大为数组长度）
    • 调整为剪枝判断，限定curPathSum>target直接砍掉（利用了数组的有序性，如果此时路径累加和已经超过target则无需进一步递归判断）

  • 去重优化

    // 当同一层如果取到同样的元素，则跳过这个分支，进而达到剪枝去重的目的
if (i > startIndex && nums[i] == nums[i - 1]) {
    continue;
}

    ​ 以【1,1,2】数组、target=3 为例进行分析：

    • 第1层startIndex=0，因此会取出1 1 2，但是对于第2个1其相当于是在同层时取出了相同元素，因此以其开头的路径可能会导致重复，因此排除这个分支，得到两个分支1 2
    • 第2层startIndex=1：
      • 对于1这个分支其可以从[1,2]中继续迭代，得到[1,1]、[1,2]🟢满足直接退出组合
      • 对于2这个分支其后面没有元素了，因此只有一个[2]组合
    • 第三层startIndex=2：
      • 对于[1,1]，可以从[2]中继续迭代，但是1+1+2=4>3 说明这个分支不满足 直接砍掉
image-20241118160515283
/**
 * 040 组合总和II
 */
public class Solution2 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径
    int curPathSum = 0; // 同步记录当前路径和

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        // 调用回溯方法
        backTrack(candidates, target, 0);
        // 返回结果
        return res;
    }


    // 回溯算法 优化版本
    public void backTrack(int[] nums, int target, int startIndex) {
        // 递归出口：遍历到集合末尾或者找到目标target
        if (curPathSum > target) { // 【优化1】剪枝
            return;
        }

        if (curPathSum == target) {
            // 处理结果(需判断重复组合) 【优化2】去重优化（在回溯过程中进行剪枝，此处则不需要重复校验，直接添加）
            res.add(new ArrayList<>(curPath)); // 将当前路径加入结果集（需new一个对象，避免引用影响）
            return;
        }

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            /*
            if (curPathSum + nums[i] > target) { // 剪枝：和递归出口那里的剪枝作用等效，校验实际不同而已
                break;
            }
             */

            // 【优化2】去重，要对同一树层使用过的元素进行跳过（可以画图理解）
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            // 1.处理节点
            curPath.add(nums[i]);
            curPathSum += nums[i];
            // 2.递归
            backTrack(nums, target, i + 1); // 不允许数组元素重复使用，此处从当前遍历节点位置的下一位开始
            // 3.复原现场
            curPath.remove(curPath.size() - 1);
            curPathSum -= nums[i];
        }
    }
}

🍚02-分割问题

🟡分割回文串（131）

1.题目内容open in new window

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案

注意此处不是要判断子串是否满足回文，而是要确定所有可能的分割方案，让分割后的所有子串满足回文，一开始想着双层循环确定子集区间的起点和终点：外层确定起点，内层确定终点，然后判断子串是否满足回文要求，但显然不符合题意

2.题解思路
👻方法1：回溯法
  • 思路分析：不断地尝试切割，将满足回文要求的切割点的子串载入路径（临时结果集），当切割点遍历到字符串末尾则切割结束
    • 回溯出口：
      • 切割位置idx遍历到字符串末尾则切割结束
    • 回溯过程：
      • 从当前切割点出发，遍历找到满足回文串的子串位置，然后再递归+回溯下一个切割点位置
      • 对于同一个位置不能重复切割，因此递归的下一个切割位置为i+1
/**
 * 131 分割回文串
 */
public class Solution2 {

    List<List<String>> res = new ArrayList<>(); // 定义结果集
    List<String> temp = new ArrayList<>(); // 定义当前的切割子串方案

    // 思路：回溯法
    public List<List<String>> partition(String s) {
        // 指定回溯算法
        backTrack(s, 0);
        // 返回结果
        return res;
    }

    // 回溯法
    public void backTrack(String s, int idx) {
        // 回溯出口（当切割点遍历到字符串末尾时将当前结果集加入集合）
        if (idx == s.length()) {
            res.add(new ArrayList<>(temp));
            return;
        }

        // 回溯过程
        for (int i = idx; i < s.length(); i++) {
            // 从切割位置开始遍历，寻找下一个切割位置，判断对应范围子串是否满足回文串，满足才有必要继续走下去
            String subStr = s.substring(idx, i + 1);
            if (isHuiWen(subStr)) {
                // 当前遍历位置i满足回文串，处理当前节点，继续递归校验
                temp.add(subStr);
                backTrack(s, i + 1); // 传入目标字符串进行递归(切割过的地方不能重复切割)
                temp.remove(temp.size() - 1);// 复原现场
            }
        }
    }

    // 判断是否满足回文
    public boolean isHuiWen(String str) {
        // 双指针判断回文
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false; // 左右不匹配，非回文，返回false
            }
            // 指针移动，继续下一个判断
            left++;
            right--;
        }
        return true;
    }

}

🟡复原IP地址（093）

1.题目内容open in new window

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
2.题解思路
👻方法1：回溯法
  • 思路分析：有点类似【分割回文串】的解法，可以基于递归切割的思路，不过此处判断的不是回文串，而是一个有效的值（值不能以0开头（但对于特例情况可以为0）且其取值范围在[0,255]）
    • 回溯出口：
      • 遍历位置到了字符串末尾则结束（return;）
        • 如果【数据刚好被划分为4块】则说明满足条件载入结果集
    • 回溯过程：
      • 从切割点开始循环遍历目标字符串，如果满足切割条件则进行递归+回溯处理
      • 路径的处理：此处选用List<String>存储切割方案，避免字符串拼接处理（增强代码可读性，后续载入结果集只需要借助String.join方法进行拼接即可）
/**
 * 093 复原IP地址
 */
public class Solution1 {

    List<String> res = new ArrayList<>(); // 定义结果集
    List<String> temp = new ArrayList<>(); // 定义临时结果（可以理解为切割路径）

    public List<String> restoreIpAddresses(String s) {
        // 长度过滤(相当于剪枝)
        if(s == null || s.length() < 4 || s.length() > 16){
            return new ArrayList<>();
        }

        // 执行回溯方法
        backTrack(s, 0);
        // 返回结果
        return res;
    }

    /**
     * 回溯算法
     */
    public void backTrack(String s, int idx) {
        // 当idx遍历到字符串末尾则结束
        if (idx == s.length()) {
            // 判断当前是否切割为4份
            if (temp.size() == 4) {
                // 满足条件，载入结果集
                res.add(String.join(".", temp));
            }
            // 退出
            return;
        }

        // 回溯过程
        for (int i = idx; i < s.length(); i++) {
            // 从当前切割位置开始，找到第一个满足切割条件的子串，然后定位下一个切割位置，递归+回溯
            String subStr = s.substring(idx, i + 1); // 注意substring切割范围：[startIndex,endIndex)
            if (subStr.equals("0") || (!subStr.startsWith("0") && Long.valueOf(subStr) <= 255)) { // 对于非0的条件判断还可加一个限制`i<idx+4`最大只有255没必要切到后面
                // 满足条件则处理节点，并执行递归+回溯
                temp.add(subStr);
                backTrack(s, i + 1); // 从下一个位置开始判断切割点（不能在重复位置切割）
                temp.remove(temp.size() - 1); // 复原现场
            }
        }
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🍚03-子集问题

🟡子集问题（078）

1.题目内容open in new window

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]
2.题解思路
👻方法1：回溯法
  • 思路分析：和【组合】的思路类似，但主要区别在于此处子集的结果收集是不需要限定条件的，因此只需要考虑收集所有不重复元素的子集即可。其和组合问题的区别可以从两个方面切入：
    • 结果的收集（组合场景是限定条件，因此要在特定条件下收集结果；而此处的子集问题是收集所有的组合，因此处理结果不需要限定条件）
    • 回溯出口（组合场景的回溯出口是遍历到叶子节点，或者是满足目标条件时停止递归；而此处的子集问题遍历到数组末尾视为递归结束，但是这个在for循环中也会自动跳出，因此加不加出口都不会影响）
    • 剪枝：子集问题不需要任何任何剪枝，其要遍历整棵树
/**
 * 078 子集
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前组合

    public List<List<Integer>> subsets(int[] nums) {
        // 调用回溯算法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 定义回溯算法
    public void backTrack(int[] nums, int startIdx) {

        // 处理结果（求不重复子集收集的是所有的结果，此处不用限定条件）
        res.add(new ArrayList<>(curPath)); // 需确认重复的集合

        // 回溯出口(startIdx==nums.length 表示遍历到数组末尾，退出)
        /*
        if (startIdx >= nums.length) { // 此处终止条件可以不加(startIndex大于数组的长度说明无元素可取需终止，此处可不加是因为当满足这个条件的时候本层for循环也结束了)
            return;
        }
         */

        // 回溯过程
        for (int i = startIdx; i < nums.length; i++) {
            curPath.add(nums[i]); // 处理节点
            backTrack(nums, i + 1); // 元素不能重复使用，递归处理
            curPath.remove(curPath.size() - 1); // 复原现场
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🟡子集II（090）

1.题目内容open in new window

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

2.题解思路
👻方法1：回溯法
  • 思路分析：最基础的做法就是构建所有子集，然后进行去重判断
    • 去重判断：
      • （1）思路1：先排序，后同一层相邻元素比较是否相等（存在相等则说明重复，需剪枝）
      • （2）思路2：先排序，set 校验（判断set集合是否已经使用过某个元素，如果是则剪枝，每次回溯遍历节点的过程都将已遍历的节点加入set）
/**
 * 090 子集II
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 此处排序，用于后续去重判断
        Arrays.sort(nums);
        // 调用回溯算法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 回溯算法
    public void backTrack(int[] nums, int startIndex) {
        // 将路径载入结果集(判断重复性)
        if (!res.contains(curPath)) {
            res.add(new ArrayList<>(curPath));
        }

        // 递归出口
//        if (startIndex >= nums.length) {
//            return;
//        }

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            // 处理节点
            curPath.add(nums[i]);
            // 递归
            backTrack(nums, i + 1);
            // 回退,复原现场
            curPath.remove(curPath.size() - 1);
        }
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

优化：去重判断（此处去重需要先对数组元素进行排序，然后在for循环过程中进行剪枝）

/**
 * 090 子集II
 */
public class Solution2 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 数组排序(用于后面去重处理)
        Arrays.sort(nums);
        // 调用回溯算法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 回溯算法
    public void backTrack(int[] nums, int startIndex) {
        // 将路径载入结果集(在回溯过程中进行了去重处理，此处直接载入子集到结果集即可)
        res.add(new ArrayList<>(curPath));

        // 递归出口
//        if(startIndex>=nums.length){
//            return;
//        }

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            // 剪枝：去除重复集合的情况，避免同一层取到同样元素（跳过当前树层使用过的、相同的元素）
            if (i > startIndex && nums[i - 1] == nums[i]) {
                continue;
            }

            // 处理节点
            curPath.add(nums[i]);
            // 递归
            backTrack(nums, i + 1);
            // 回退,复原现场
            curPath.remove(curPath.size() - 1);
        }
    }
}

/**
 * 090 子集II
 */
public class Solution3 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 数组排序(用于后面去重处理)
        Arrays.sort(nums);
        // 调用回溯算法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 回溯算法
    public void backTrack(int[] nums, int startIndex) {
        // 将路径载入结果集(在回溯过程中进行了去重处理，此处直接载入子集到结果集即可)
        res.add(new ArrayList<>(curPath));

        // 递归出口
//        if(startIndex>=nums.length){
//            return;
//        }
        // set 做去重判断
        HashSet<Integer> hs = new HashSet<>();

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            // 剪枝：去除重复集合的情况，避免同一层取到同样元素
            if (!hs.isEmpty() && hs.contains(nums[i])) {
                continue;
            }

            hs.add(nums[i]); // 记录已遍历节点

            // 处理节点
            curPath.add(nums[i]);
            // 递归
            backTrack(nums, i + 1);
            // 回退,复原现场
            curPath.remove(curPath.size() - 1);
        }
    }
}

🟡非递减子序列（491）

1.题目内容open in new window

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]
2.题解思路
👻方法1：回溯法
  • 思路分析：题目中限定是子序列概念，因此不可以对原数组进行排序，保持现有序列进行判断
    • 只要路径节点超过1个，就加入满足条件的路径（升序校验是在回溯过程中将当前遍历节点与curPath的最后一个节点进行比较，不满足则直接剪掉（基于此不需要每次都去判断一个完整的子序列是否为升序））
    • 对于路径重复的情况，则是通过set进行去重

/**
 * 491 非递减子序列
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>(); // 定义当前路径

    public List<List<Integer>> findSubsequences(int[] nums) {
        // 调用回溯方法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 回溯方法
    public void backTrack(int[] nums, int startIndex) {

        // 满足条件则加载结果集（递增子序列）
        if (curPath.size() >= 2) {
            res.add(new ArrayList<>(curPath)); // 加入满足条件的路径
        }

        HashSet<Integer> hs = new HashSet<>();

        // 回溯过程
        for (int i = startIndex; i < nums.length; i++) {
            // 剪枝：如果当前路径的最后一个元素大于当前遍历元素值（说明出现降序，可以跳过这个分支），或者当前元素已经遍历过了
            if (!curPath.isEmpty() && curPath.get(curPath.size() - 1) > nums[i] || hs.contains(nums[i])) {
                continue;
            }
            hs.add(nums[i]);

            curPath.add(nums[i]); // 处理节点
            backTrack(nums, i + 1); // 递归
            curPath.remove(curPath.size() - 1); // 复原现场
        }
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🍚04-排列问题

🟡全排列open in new window（046）

1.题目内容

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]
2.题解思路
👻方法1：回溯法（交换元素思路）
  • 思路分析：先固定一个全序列，然后通过递归交换元素的方式构建新序列返回，当idx遍历到数组最后一个元素时（表示没有元素交换）记录结果

    • 根据【回溯算法】模板进行设计，此处对比【子集问题】

      • 子集的结果集是覆盖了所有节点的路径（其结果集），而对于全排列则是要在叶子节点处记录结果集

    • 全排列的核心思路：递归处理时固定[0,idx)的排列，然后对于[idx,len-1]的内容，每次循环将属于[idx,len-1]的元素x与idx位置进行交换（相当于得到这部分的全排列，得到以每个x为开头的序列进行拼接）

/**
 * 046 全排列
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 调用回溯方法
        backTrack(nums, 0);
        // 返回结果
        return res;
    }

    // 定义回溯方法
    public void backTrack(int[] nums, int idx) {
        // 回溯出口
        if (idx >= nums.length) { // path.size() == nums.length（全排列的路径长度与数组元素长度一致）
            // 表示遍历到叶子节点才将结果载入
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 回溯过程
        for (int i = idx; i < nums.length; i++) {
            // 处理节点：交换位置，载入节点路径（此处注意curPath的元素的添加受到swap的影响，如果是swap之前添加则加入nums[i],如果是swap之后添加则加入nums[idx]（因为swap之后i与idx位置的元素已经相互交换））
            swap(nums, i, idx);
            curPath.add(nums[idx]);
            // 递归调用
            backTrack(nums, idx + 1); // 处理下个位置
            // 复原现场
            swap(nums, idx, i);
            curPath.remove(curPath.size() - 1);
        }
    }

    // 交换指定索引位置的数组元素
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

  • 复杂度分析

    • 时间复杂度：N为数组nums的长度

    • 空间复杂度：全排列递归深度为N（系统累计使用栈空间大小为O（N））

另一种写法（推荐🚀）：基于原地的List交换，记录当前交换的序列

​ 这种思路的写法不是上面这种拼接curPath路径节点，而是一开始就确定一条完整路径，随后通过交换元素的方式记录交换后的每一种可能的排列，因此其回溯出口是当遍历到集合最后一个元素，没有需要交换的内容时就记录结果集。因此此处先将数组nums转为list形式便于处理结果集，在回溯的过程中不需要拼接节点，只需要记录结果集即可

/**
 * 046 全排列
 */
public class Solution2 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集

    public List<List<Integer>> permute(int[] nums) {

        // 将数组转为list
        List<Integer> curPath = new ArrayList<>();
        for (int num : nums) {
            curPath.add(num);
        }

        // 调用回溯方法
        backTrack(curPath, 0);
        // 返回结果
        return res;
    }

    // 定义回溯方法(此处处理的是nums序列)
    public void backTrack(List<Integer> nums, int idx) {
        // 回溯出口
        if (idx == nums.size() - 1) {
            res.add(new ArrayList<>(nums)); // 当遍历到数据末尾最后一个元素，说明不需要继续进行交换了，直接记录当前序列
            return;
        }

        // 回溯过程
        for (int i = idx; i < nums.size(); i++) {
            // 处理节点：交换位置，载入节点路径
            Collections.swap(nums, i, idx);
            // 递归调用
            backTrack(nums, idx + 1); // 处理下个位置
            // 复原现场
            Collections.swap(nums, idx, i);
        }
    }
}
👻方法2：回溯法（全排列思路）
  • 思路分析：核心关注每次递归起始为0（不需要startIndex），且要排除当前路径已经遍历过的元素
    • 区别：从for循环的起点中切入，上述方法1的版本是通过idx准确地来说可以理解为是交换的起始位置
    • 排列是有序的，因此对于已经使用过的元素还可以再次重复使用，因此排列中每次for循环的起点都要从0开始处理（但需排除掉curPath中已经选择的元素）
      • 例如[1,2]、[2,1] 虽然元素1被重复使用，但是基于排列的有序性考虑，这两个集合代表的是不同的集合
      • 而对于子集而言[1,2]和[2,1]表示的是相同的集合
    • 案例分析：每次选择一个元素，然后递归从头开始选择一个当前路径还没选过的元素
      • 【1 2 3】：
        • 第1步 选了1，随后继续递归【2 3】（此处排除1是因为路径已经选择1，所以后面递归的过程中不能选择重复的元素）
          • 第2步 选了2，随后继续递归【3】（同理路径已经选了2，不能重复选择），最终得到【1 2 3】
          • 第2步 选择3，随后继续递归【2】，最终得到【1 3 2】
        • 第1步 选择2，随后递归【1 3】，以此类推，得到【2 1 3】【2 3 1】
        • 第1步 选择3，随后递归【1 2】，以此类推，得到【3 1 2】【3 2 1】
/**
 * 046 全排列
 */
public class Solution3 {

    List<List<Integer>> res = new ArrayList<>(); // 定义结果集
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 调用回溯方法
        backTrack(nums);
        // 返回结果
        return res;
    }

    // 定义回溯方法
    public void backTrack(int[] nums) {
        // 回溯出口
        if (curPath.size() == nums.length) { // 当当前路径的长度和数组长度一致说明构成了一个排列顺序
            // 表示遍历到叶子节点才将结果载入
            res.add(new ArrayList<>(curPath));
            return;
        }

        // 回溯过程（排列：每次都从0开始检索，但需排除掉已经存在于路径的元素）
        for (int i = 0; i < nums.length; i++) { // for 循环处理（注意此处的起点）
            // 判断当前路径是否已经包含该元素，如果包含则剪掉
            if(curPath.contains(nums[i])){
                continue;
            }

            curPath.add(nums[i]); // 处理节点
            backTrack(nums); // 递归调用
            curPath.remove(curPath.size() - 1); // 复原现场
        }
    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🟡全排列II（047）

1.题目内容open in new window

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2.题解思路
👻方法1：回溯法（全排列思路）
  • 思路分析：全排列+剪枝
/**
 * 047 全排列
 */
public class Solution1 {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> curPath = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);

        // 排序
        Arrays.sort(nums);

        // 调用回溯方法
        backTrack(nums, used);
        // 返回结果
        return res;
    }

    // 回溯算法
    public void backTrack(int[] nums, boolean[] used) {
        if (curPath.size() == nums.length) {
            res.add(new ArrayList<>(curPath));
            return;
        }
        // 回溯过程
        for (int i = 0; i < nums.length; i++) {
            /**
             * used[i - 1] == true 说明同⼀树⽀nums[i - 1]使⽤过;
             * used[i - 1] == false 说明同⼀树层nums[i - 1]使⽤过;
             * 如果同⼀树层nums[i - 1]使⽤过则直接跳过(i > 0 && nums[i - 1] == nums[i],同一数层中使用过的元素可以跳过（需对nums排序才能判断相邻）)
             */
            if ((i > 0 && nums[i - 1] == nums[i]) && used[i - 1] == false) { // 对于路径而言 used[i - 1]要一直为true或者一直为false 校验才有意义
                continue;
            }
            // 如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                // 回溯过程核心
                curPath.add(nums[i]);// 处理节点
                used[i] = true;
                backTrack(nums, used); // 递归处理
                curPath.remove(curPath.size() - 1); // 复原现场
                used[i] = false;
            }
        }
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

👻方法2：回溯法（交换元素思路🚀）基于【047-全排列】的交换元素思路的回溯法进行去重的剪枝处理

​ 先固定一个全序列，然后通过递归交换元素（注意去重剪枝）的方式构建新序列返回，当idx遍历到数组最后一个元素时（表示没有元素交换）记录结果

  • 思路分析：在方法1中加入重复元素的判断，可以看到这个重复集合校验的版本和【子集II 090】中重复集合的校验版本中的处理是类似的，通过set进行控制。只不过此处不需要先对数组进行排序，因为对于全排列而言（不能打乱其原有的顺序）顺序也是一个校验条件（[1 2]、[2 1]是两个不同的序列）
/**
 * 047 全排列
 */
public class Solution2 {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> curPath = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            curPath.add(nums[i]);
        }
        // 调用回溯方法
        backTrack(curPath, 0);
        // 返回结果
        return res;
    }

    // 回溯算法
    public void backTrack(List<Integer> nums, int idx) {
        if (idx == nums.size() - 1) { // idx 遍历到元素的最后一个元素，后面没有元素可以交换了，加载结果集
            res.add(new ArrayList<>(new ArrayList<>(nums)));
            return;
        }

        HashSet<Integer> set = new HashSet<>();

        // 回溯过程
        for (int i = idx; i < nums.size(); i++) {

            // 去重处理
            if(!set.isEmpty()&&set.contains(nums.get(i))){
                continue; // 重复，剪枝
            }
            set.add(nums.get(i));

            // 交换元素
            Collections.swap(nums, idx, i);
            // 递归
            backTrack(nums, idx + 1);
            // 复原现场
            Collections.swap(nums, i, idx);
        }
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🍚05-棋盘问题

🔴N皇后（051）

同样的：【052-N皇后II】问题求的是解决方案的数量，相应地将结果的处理转化为计数即可

1.题目内容open in new window

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

image-20241119133221317

2.题解思路

问题分析

​ 结合题意理解N皇后的约束条件：[row,col]

  • 不能同行（校验row相同的元素）
  • 不能同列（校验col相同的元素）
  • 不能同斜线（需校验45度、135度的斜线情况）

​ 以 3 × 3 的棋盘为例，将搜索过程抽象为一棵树，则分析如下：

  • 可以看到二维矩阵中矩阵的高就是树的高度，矩阵的宽就是树形结构中每个节点的宽度
  • 基于皇后们的约束条件，只要检索到叶子节点（可以理解为路径中节点个数:curPath.sisze() = 树的高度:二维矩阵高度）
image-20241119133629480

​

// 回溯模板
public void backTrack(参数){
	if(终止条件){
        // 记录结果
        return;
    }
    
    for(选择：本层集合中的元素){
        // 1.处理节点
        // 2.递归（backTrack(路径，选择列表)）
        // 3.回溯（撤销处理结果，恢复现场）
    }
}
👻方法1：回溯法

  • 思路分析：路径（二维矩阵）+for 选择列、递归 选择行+剪枝（校验当前选择位置是否满足存放条件）

    • （1）基于回溯模板将基础算法结构确定下来（需注意此处的路径存储概念由List<String> curPath调整为char[][] chessBoard便于存储管理）

      • 路径：此处的路径不局限于List<String> curPath这种形式定义，此处的路径记录的应该是整个棋盘的状态，因为在选择路径的过程中需要对皇后的存放位置进行校验（使用char[][] chessBoard存储的是棋盘的实时状态，基于二维矩阵可以方便地用索引来确定同行、同列、对角线是否已经存在了Q，在封装结果集的时候再转一道即可）

    • （2）剪枝：只有满足N皇后的存放条件才会继续递归路径，否则进行剪枝

      • （a）回溯算法中for循环传入的row验证都是同一层，因此不用额外验证row

      • （b）同一列判断：列不变，行的取值为[0, row) (当前节点及后面的位置还没选，不需要验证)

      • （c）对角线判断：

        • 左上对角线验证：起点是[row-1,col-1], 终点条件（不能超出边界条件i>=0 && j>=0）, 遍历方向（i--,j--）
        • 右上对角线验证：起点是[row-1,col+1], 终点条件（不能超出边界条件i>=0 && j<=n-1）, 遍历方向（i--,j++）
        • 左下、右下的对角线还没有选到该行，暂时不需要进行校验
        • 针对对角线校验常见误区：
          • ❌双层for处理错误：此处应该是校验对角坐标，因此i、j应该是同步移动的（放在同一个for循环中处理），如果构建了双层for循环，那么遍历的范围就会变成校验某一行的指定范围列（实际只需要校验对角线位置的坐标）
          • ❌校验方向错误：在处理过程中可能会习惯性从上往下、从左往右的顺序，但是此时选定的位置并不一定是满足m*m的坐标关系，那么就会导致不同的校验方向产生不同的校验结果（可以结合下述图示分析，以左对角线为例：如果采用从上到下从左往右的遍历方向，这个对角线的位置就会偏移，显然是错误的）。因此对于遍历方向的选择，以选定的节点坐标[row,col]出发=》向边界靠拢，才能定位正确的对角线元素

        image-20241119151704407

/**
 * 051 N皇后
 */
public class Solution051_02 {

    List<List<String>> res = new ArrayList<>(); // 定义结果集
    // List<String> path = new ArrayList<>(); // 定义当前选择路径（每个String表示每一行N皇后的选择方案）

    public List<List<String>> solveNQueens(int n) {
        // ① 初始化棋盘
        char[][] chessBoard = new char[n][n];
        for (char[] row : chessBoard) {
            Arrays.fill(row, '.');
        }
        // ② 调用回溯算法
        backTrack(n, 0, chessBoard);
        // ③ 返回结果
        return res;
    }

    /**
     * 定义回溯算法：由于N皇后存放的限制条件需要校验当前的整合棋盘的行、列、对角线，因此构建二维矩阵处理会比较方便
     * 如果只是存储curPath路径，则还要根据目前现有的res去复盘整个棋局，不如直接用二维矩阵处理，然后再将最终生成的二维矩阵转化为结果集
     *
     * @param n   矩阵大小
     * @param row 当前遍历行
     * @param chessBoard 棋盘
     */
    public void backTrack(int n, int row, char[][] chessBoard) {
        // 递归出口
        if (row == n) {
            // 将当前路径封装到res(记录当前棋盘的状态)
            res.add(outputChess(chessBoard));
            return;
        }

        // 递归处理
        for (int j = 0; j < n; j++) { // 每一行从[0,n)中择选放置的列
            if (isValid(chessBoard, row, j)) { // 校验当前位置放置棋子是否合理，如果合理才放置
                // 处理
                chessBoard[row][j] = 'Q';
                // 递归
                backTrack(n, row + 1, chessBoard);
                // 回溯
                chessBoard[row][j] = '.';
            }
        }
    }

    /**
     * 校验当前放置N皇后位置是否合理(遍历判断整个棋盘，不能同行、同列、同斜线方向)
     * @param chessBoard 棋盘
     * @param row   当前选择的行
     * @param col   当前选择的列
     */
    public boolean isValid(char[][] chessBoard, int row, int col) {
        // 同行校验（同行校验范围：列[0,j)）：回溯过程限定了每一列按列处理，确保了同一行不会出现多个Q，此处可以省略校验

        // 同列校验（同列校验范围：行[0,row)）
        for (int i = 0; i < row; i++) {
            if (chessBoard[i][col] == 'Q') {
                return false; // 同列位置上已存在`Q`，这个位置不符合放置条件
            }
        }

        // 同斜线方向校验(左上对角线：[0,0]-[row-1,col-1]、右上对角线：[row-1,col+1]-[0,n-1])
        // ① 左上对角线校验：从下到上，从右到左
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessBoard[i][j] == 'Q') {
                return false; // 45度对角出现过了皇后，因此这个位置不能放
            }
        }

        // ② 右上对角线：从下到上，从左到右
        for (int i = row - 1, j = col + 1; i >= 0 && j < chessBoard.length; i--, j++) {
            if (chessBoard[i][j] == 'Q') {
                return false; // 右上对角线位置上已存在Q，这个位置不符合放置条件
            }
        }

        // 通过上述校验
        return true;
    }

    // 将当前棋盘放置结果输出
    public List<String> outputChess(char[][] chessBoard) {
        List<String> list = new ArrayList<>();
        for (char[] row : chessBoard) {
            list.add(String.copyValueOf(row)); // char 处理：String.copyValueOf(c)
        }
        return list;
    }

//    public static void main(String[] args) {
//        Solution051_02 s = new Solution051_02();
//        s.solveNQueens(4);
//    }
}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

​ 上述解法的核心思路在于回溯算法的设计，对每一行的选择进行递归、回溯，而每一行又可以从指定的列范围内选择有效的放置位置（即校验当前位置是否满足N皇后条件，如果满足才进行放置）

​ 针对【052-N皇后II】则不需要记录每个满足条件的棋盘状态，因此将上述解法中的res调整为方案数统计即可，每找一个满足条件的方案则进行累加统计

/**
 * 051 N皇后
 */
public class Solution052_01 {

    public int res = 0; // 定义方案数

    public int totalNQueens(int n){
        // ① 初始化棋盘
        char[][] chessBoard = new char[n][n];
        for (char[] row : chessBoard) {
            Arrays.fill(row, '.');
        }
        // ② 调用回溯算法
        backTrack(n, 0, chessBoard);
        // ③ 返回结果
        return res;
    }

    /**
     * 定义回溯算法：由于N皇后存放的限制条件需要校验当前的整合棋盘的行、列、对角线，因此构建二维矩阵处理会比较方便
     * 如果只是存储curPath路径，则还要根据目前现有的res去复盘整个棋局，不如直接用二维矩阵处理，然后再将最终生成的二维矩阵转化为结果集
     *
     * @param n   矩阵大小
     * @param row 当前遍历行
     * @param chessBoard 棋盘
     */
    public void backTrack(int n, int row, char[][] chessBoard) {
        // 递归出口
        if (row == n) {
            // 找到一种满足条件的方案
            res++;
            return;
        }

        // 递归处理
        for (int j = 0; j < n; j++) { // 每一行从[0,n)中择选放置的列
            if (isValid(chessBoard, row, j)) { // 校验当前位置放置棋子是否合理，如果合理才放置
                // 处理
                chessBoard[row][j] = 'Q';
                // 递归
                backTrack(n, row + 1, chessBoard);
                // 回溯
                chessBoard[row][j] = '.';
            }
        }
    }

    /**
     * 校验当前放置N皇后位置是否合理(遍历判断整个棋盘，不能同行、同列、同斜线方向)
     * @param chessBoard 棋盘
     * @param row   当前选择的行
     * @param col   当前选择的列
     */
    public boolean isValid(char[][] chessBoard, int row, int col) {
        // 同行校验（同行校验范围：列[0,j)）：回溯过程限定了每一列按列处理，确保了同一行不会出现多个Q，此处可以省略校验

        // 同列校验（同列校验范围：行[0,row)）
        for (int i = 0; i < row; i++) {
            if (chessBoard[i][col] == 'Q') {
                return false; // 同列位置上已存在`Q`，这个位置不符合放置条件
            }
        }

        // 同斜线方向校验(左上对角线：[0,0]-[row-1,col-1]、右上对角线：[row-1,col+1]-[0,n-1])
        // ① 左上对角线校验：从下到上，从右到左
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessBoard[i][j] == 'Q') {
                return false; // 45度对角出现过了皇后，因此这个位置不能放
            }
        }

        // ② 右上对角线：从下到上，从左到右
        for (int i = row - 1, j = col + 1; i >= 0 && j < chessBoard.length; i--, j++) {
            if (chessBoard[i][j] == 'Q') {
                return false; // 右上对角线位置上已存在Q，这个位置不符合放置条件
            }
        }

        // 通过上述校验
        return true;
    }

}

🔴解数独（037）

1.题目内容open in new window

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

image-20241119154737483
2.题解思路
👻方法1：双层递归回溯

  • 核心：双层循环校验每个位置放置是否合适，如果合适则继续递归放置下一个位置（对于已经放过的位置直接跳过即可）

  • 思路分析：一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性

    • 回溯算法boolean backTrack(char[][] board)

      • 此处定义的回溯算法是存在返回值的，当校验出现满足条件的存放位置即返回true（内部递归回溯算法返回true则视作当前路径满足放置条件），当指定位置没有可放置的数字则说明当次选择路径走不下去（返回false）

    • 双层for循环遍历当前位置[i,j]

      • 如果board[i][j]已经填充过数字则跳过（每一层递归都会从头开始校验可以存放的位置，已经填充则直接跳过即可，不用纠结递归是否会重复存放）
      • 如果board[i][j]还没填充过数字（即不为.），则从1-9的数字字符数中依次尝试填入，并校验当前位置填充该元素是否合适（行、列、九宫格）
        • 如果校验不通过：剪枝处理
        • 如果校验通过：则进一步递归尝试填充下一个位置元素
          • 处理节点：填充board[i][j]元素
          • 递归：此处递归设定返回值，一旦找到合适的组合则直接返回true
          • 恢复现场：恢复board[i][j]为.

    • 九宫格有效性校验：boolean validBoard(char[][] board, int row, int col, int val)

      • 校验行（整行校验）：列固定（需注意，此处board已经预填充了一些数字，因此需要校验整行的内容）

      • 校验列（整列校验）：行固定（同理，此处board已经预填充了一些数字，因此需要校验整列的内容）

      • 校验九宫格：找到当前位置对应的九宫格起点、终点，构建循环遍历看当前val是否出现过

        • startRow = (row / 3) * 3；startCol = (col / 3) * 3; 确定[row,col]所在的九宫格起点（即对应所在九宫格的最左上角元素）

          image-20241119164319743
/**
 * 037 解数独
 */
public class Solution1 {

    public void solveSudoku(char[][] board) {
        // 调用回溯算法
        backTrack(board);
    }


    // 定义回溯算法
    public boolean backTrack(char[][] board) {

        // 双层循环放置元素，确定某个位置存放1-9是否合适，合适则递归存放下一个位置
        for (int i = 0; i < board.length; i++) { // 遍历行
            for (int j = 0; j < board[0].length; j++) { // 遍历列
                // 如果当前位置已经放过数据了，则直接跳过
                if (board[i][j] != '.') {
                    continue;
                }

                // 如果当前位置为空即'.'，判断当前位置是否适合放某个数字（从1-9）
                for (char num = '1'; num <= '9'; num++) {
                    // 校验[i,j]这个位置放这个数字是否合适，如果不合适则跳过
                    if (!validBoard(board, i, j, num)) {
                        continue;
                    }

                    // 如果这个位置存放当前数字合适，则做相应处理（节点处理、递归、回溯）
                    board[i][j] = num;
                    if (backTrack(board)) {
                        return true; // 如果找到合适的立刻返回 backTrack(board);
                    }
                    board[i][j] = '.';
                }
                // 9个数都试完了，没找到合适的数存放，说明该方案不行
                return false;
            }
        }
        // for 循环遍历结束没有返回false，说明找到了合适的棋盘位置
        return true;
    }

    // 校验九宫格是否有效
    public boolean validBoard(char[][] board, int row, int col, int val) {
        // 校验行
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) {
                return false; // 遍历到指定行的某一列发现该元素已经出现过了
            }
        }

        // 校验列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == val) {
                return false; // 遍历到指定列的某一行发现该元素已经出现过了
            }
        }

        // 校验九宫格
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

}

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

🎈06-其他问题

🔴重新安排行程（322）

参考题解open in new window

1.题目内容open in new window

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次

image-20241119131925402

2.题解思路
👻方法1：

  • 复杂度分析

    • 时间复杂度：

    • 空间复杂度：

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
一人の境 Copyright © 2019-未知 holic-x
Copyright © 2025 holic-x