算法基础day 9~11 递归回溯

---

---

👉day09 递归/回溯

回溯算法和 DFS 算法⾮常类似，本质上就是⼀种暴⼒穷举算法。

回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」

可以直接把回溯算法当成多层的for循环来理解, 其实就是通过递归来少些多层的for循环

78. 子集

难度中等1765

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

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

回溯算法思路

本质上子集问题就是遍历这样用一棵回溯树：

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> track=new LinkedList<>();// 记录走过的路径
    public List<List<Integer>> subsets(int[] nums) {
        backTrack(nums,0);
        return res;
    }
    void backTrack(int[]nums,int start){
        res.add(new LinkedList<>(track));
        for (int i = start; i < nums.length; i++) {
            track.addLast(nums[i]);// 做选择
            backTrack(nums,i+1);// 注意这个地方是i+1, 不要写成start +1 , 如果是start+1 那么就会添加重复的元素
            track.removeLast(); // 撤销选择
        }
    }
}

90. 子集 II

难度中等912

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

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

本题是上一题的进阶版本, 需要注意的就是要避免回溯相同的元素:

具体的避免的操作:

1. 排序数组, 使相同的元素靠在一起

2. 在回溯的时候加一个判断, 如果当前的元素与前一个元素相同,就跳过

   注意不要忘记第一个回溯的元素不需要跳过 : 因此需要i>start

具体的操作的代码:

if(i>start&&nums[i]==nums[i-1]){

​ continue;

​ }

那么在上一题的答案中稍作修改即可:

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> track=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); //先排序, 让相同的元素靠在一起
        backTrack(nums,0);
        return res;
    }
    void backTrack(int[]nums,int start){
        res.add(new LinkedList<>(track));
        for (int i = start; i < nums.length; i++) {
            if(i>start&&nums[i]==nums[i-1]){ // 跳过重复的元素
                continue;
            }
            track.addLast(nums[i]);
            backTrack(nums,i+1);// 注意这个地方是i+1, 不要写成start +1 , 如果是start+1 那么就会添加重复的元素
            track.removeLast();
        }
    }
}

👉day10 递归/回溯

47. 全排列 II

难度中等1173

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

• 使用vis数组统计走过的元素, 通过具体的题意来确定下一次回溯的起始坐标 ,
  1. 比如一个元素可以利用多次, 那么下一次回溯的起始下标就可以继续从当前的 i 进行
  2. 如果题目说明了一个元素只能用一次, 那么下一次回溯的起始下标就是 i+1

跳过重复元素的判断条件:

1. 首先当前的元素不能是第一个元素 :i>start
2. 当前元素要与前一个元素相同 :nums[i]==nums[i-1]
3. 前一个相同的元素在上一次使用过 , 因此当前的元素为了避免重复就不能在使用了

关于vis数组:

• vis[i - 1] == true，说明同一树枝nums[i - 1]使用过
• vis[i - 1] == false，说明同一树层nums[i - 1]使用过
• 如果同一树层nums[i - 1]使用过则直接跳过

class Solution {
    boolean []vis=new boolean[9];
    List<List<Integer>> res=new ArrayList<>();
    void backTrack(int[]nums,LinkedList<Integer>track){
        if(track.size()==nums.length){
            res.add(new LinkedList<>(track));
            return ;
        }
        for (int i = 0; i < nums.length; i++) {
            if(vis[i]) continue;
            if(i>0&&nums[i]==nums[i-1]&&!vis[i-1]){
                continue;
            }
            vis[i]=true;
            track.addLast(nums[i]);
            backTrack(nums,track);
            vis[i]=false;
            track.removeLast();
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums); //先排序, 让相同的元素靠在一起
        backTrack(nums,new LinkedList<>());
        return res;
    }
}

对于这种有I , II , III 多个版本的题目, 有一种十分舒服的方法,

• 先把难度最大的III写了再回头去看后面的题目, 就迎刃而解了😭

39. 组合总和

难度中等2136

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

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

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

本题的注意事项:

1. candidates 中的每个数字在每个组合中只能使用 一次 。
2. 需要去除重复的数字, 但是注意 同一个 数字可以 无限制重复被选取

上代码

class Solution { //candidates 中的每个数字在每个组合中只能使用 一次 。
    public List<List<Integer>> combinationSum(int[] candidates, int target) { //candidates 注意去除重复的元素!!
        //! 重复的数字还是需要去除的, 因为如果有重复的数字, 那么就一定会有重复的情况
        Arrays.sort(candidates);
        backTrack(candidates,target,0);
        return res;
    }
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> track=new LinkedList<>();
    void backTrack(int[]nums,int target,int start){
        if(target<0) return ;
        if(target==0){
            res.add(new LinkedList<>(track));
            return ;
        }
        for (int i = start; i < nums.length; i++) {
           if(i>0&&nums[i]==nums[i-1]) continue; // 跳过相同的元素
            if(nums[i]>target) continue; // 剪枝 , 快了3ms , 13% -> 99%
            track.addLast(nums[i]);
            backTrack(nums,target-nums[i],i);// 
            track.removeLast();
        }
    }
}

40. 组合总和 II

难度中等1085

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

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

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

本题思路与上一题基本一致 , 区别就是本题中的每一个数字只能使用一次

• 借助boolean []vis 来存储每一个元素是否被访问过

vis[i] 表示下标为i的元素的访问状态

• true表示访问过
• false表示没有访问过

backTrack(nums,target-nums[i],i+1); 与上一题的 backTrack(nums,target-nums[i],i);不一样 ,

• 因为上一题的每个元素可以重复使用, 因此继续从当前元素的下标开始

class Solution { //candidates 中的每个数字在每个组合中只能使用 一次 。
    public List<List<Integer>> combinationSum2(int[] candidates, int target) { //candidates 注意去除重复的元素!!!---
        //! 重复的数字还是需要去除的, 因为如果有重复的数字, 那么就一定会有重复的情况
        Arrays.sort(candidates);
        vis=new boolean[candidates.length];
        backTrack(candidates,target,0);
        return res;
    }
    boolean []vis;
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> track=new LinkedList<>();
    void backTrack(int[]nums,int target,int start){
        if(target<0) return ; // 剪枝
        if(target==0){
            res.add(new LinkedList<>(track));
            return ;
        }
        for (int i = start; i < nums.length; i++) {
           if(i>0&&nums[i]==nums[i-1]&&!vis[i-1]) continue; // 跳过相同的元素
            // if() continue;
            if(target<nums[i]) continue; //剪枝
            vis[i]=true;
            track.addLast(nums[i]);
            backTrack(nums,target-nums[i],i+1);
            vis[i]=false;
            track.removeLast();
        }
    }
}

👉day11 递归/回溯

17. 电话号码的字母组合

思路

难度中等2075

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

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

回溯算法

通俗易懂+动画演示 17. 电话号码的字母组合 - 电话号码的字母组合 - 力扣（LeetCode）

变量解释:

1. String[]letters用来存储数字对应的字母
   • 注意 1 以及 0 不代表任何字母, 前两个要空出来

可以通过设置全局变量来减少函数参数传递的参数

• String digits;

class Solution {
    String[]letters=new String[]{
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
    };
    LinkedList<String> res=new LinkedList<>();
    String digits;
    public List<String> letterCombinations(String digits) { //"235"
        if(digits.equals("")) return res;
        this.digits=digits;
        backTrack(0,new StringBuilder());
        return res;
    }
    void backTrack(int idx ,StringBuilder track){
        if(track.length()==digits.length()){
            res.add(track.toString());
            return ;
        }
        String curLetter = letters[digits.charAt(idx) - 0x30]; // 当前的数字对应的字符串
        for (int i = 0; i < curLetter.length(); i++) {
            track.append(curLetter.charAt(i));
            backTrack(idx+1,track); //回溯 , 
            track.deleteCharAt(track.length()-1);
        }
    }
}

79. 单词搜索

难度中等1422

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

DFS

• 先在外层遍历表格, 当表格中的元素与word的首个元素相同时, 开始递归
• 使用vis[][] 来记录一次搜索的过程中访问过的元素
  • 或者也可以不用vis[][] ,可以更改表格的元素, 搜索结束时候再改回来
• 使用idx 来记录符合单词的顺序的字符的个数, 当idx==word.length() 返回true 即可

话不多说, 上代码

class Solution {
    boolean res=false;
    boolean [][]vis;
    String word;
    public boolean exist(char[][] board, String word) {
        this.word=word;
        vis=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]==word.charAt(0))
                    dfs(board,i,j,0);
                if(res) return true; // 提前返回
            }
        }
        return false;
    }
    public void dfs(char[][]board ,int i,int j,int idx){
        if(idx==word.length()){ // 如果当前的idx 的符合条件的字符的长度等于 word的长度, 说明表格中存在单词 ,直接return, 
            res=true; //把这个写在越界的上面 ,是因为有 [["a"]] 的情况, 'a' , 即使包含a , 但下一次dfs 也因为 越界提前返回了
            return;
        }
        if(i<0||j<0||i>=board.length||j>=board[0].length) // 越界
            return ;
        if(vis[i][j]) return ;
        vis[i][j]=true;
        if(!(board[i][j]==word.charAt(idx))){
            vis[i][j]=false; // 注意需要恢复 访问状态, 否则会影响下一次的dfs
            return ;
        }
        dfs(board,i+1,j,idx+1);
        dfs(board,i,j-1,idx+1);
        dfs(board,i,j+1,idx+1);
        dfs(board,i-1,j,idx+1);
        vis[i][j]=false;
    }
}

22. 括号生成

难度中等2835

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

首先, 我们需要明白

有效的括号组合

• 右括号左边的左括号一定是大于等于右括号的数量

思路

• 分别统计左右括号的剩余数量, 然后开启分支(DFS)
  • left大于0 即可开启
  • right需要 right>left才可以开启分支,
    • 注意有效括号的条件
  • left , right 表示左右括号可以使用的剩余的数量
    • left right 初始化为n

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("",n,n);
        return res;
    }
    void dfs(String cur, int left, int right){ // left right 分别统计剩余的左右括号  ,cur 表示当前的字符串
        if(left==0&&right==0){ // 左右括号都用完了 , return
            res.add(cur);
            return ;
        }
        if(left>0){ // 剩余的 左括号还有
            dfs(cur+"(",left-1,right);
        }
        if(right>left){  // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            dfs(cur+")",left,right-1);
        }
    }
}

👉同类型题目

77. 组合

难度中等1063

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

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

即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此需要按某种顺序展开搜索，这样才能做到不重不漏。

临界点计算：

本题的临界点就是 刚好这个位置的数字(x) x+k>n 恰好大于n, 也就是让 x+k=n+1;

可以得出临界点就是 x= n+k-1;(可以等于，举例n=4 k=3尝试即可)

• 例如当start=3时， 此时即便是 将后面的4 加上去， 本轮的list也无法凑够3个数字，因此直接省略本轮循环即可

class Solution {
     List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) { 
        getCombine(n, k, 1, new ArrayList<>());
        return res;
    }
public void getCombine(int n,int k,int start,List<Integer> list){
        if(k==0) {// 说明此时list 已经存入了k个数字
            res.add(new ArrayList(list)) ; 
            return ;
        } 
        //i小于等于临界点即可 ，
        for(int i=start;i<=n-k+1;i++){
            list.add(i);
            getCombine(n, k-1, i+1, list);
            list.remove(list.size()-1);
//list 用来存储数字(list.add(i))，存够了k个数字就 返回然后每次删除list末尾的数字(list.remove(list.size-1))->也就是移除末尾的数字
        }
        return ;
    }
}

46. 全排列

难度中等2132

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

• 即 [1, 2, 3] 与 [1, 3, 2] 不认为是同一个组合

nowIndex用于记录当前的个数，如果==nums.length ，说明本轮的 list 中的元素个数够了，返回即可。

vis用来记录当前下标 的元素是否访问过，

如果访问过了就直接跳过，不add

如果没有访问过，就标记为true ，然后将对应下标的元素添加到list中，

注意这里返回的是上一层函数（即前一个位置），并在这里执行vis[i] = 0将标记清除

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        boolean []vis=new boolean[len];
        dfs(0,nums,vis,new ArrayList<>());
        return res;
    }
    public void dfs(int nowIndex,int[]nums,boolean[]vis,List<Integer> list){
        if(nowIndex==nums.length) {
            res.add(new ArrayList(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(vis[i]){
                continue ;
            }
            list.add(nums[i]);
            vis[i]=true;
            dfs(nowIndex+1,nums,vis,list);
            vis[i]=false;
            list.remove(list.size()-1);
        }
    }
}

小知识

• X ^32 =x （X 表示大写字母， x表示小写字母）

img

我们发现大写字符与其对应的小写字符的 ASCII 的差为 32，32 这个值如果敏感的话，它是 2⁵，

在编程语言中，可以表示为 1 << 5。而变换大小写这件事等价于：

• 如果字符是小写字符，减去 32 得到大写字符；
• 如果字符是大写字符，加上 32 得到小写字符。

而这两者合并起来，就是给这个字符做一次不进位的加法，即异或上 1 << 5。

• 将 小写字母与大写字母对应的二进制表示对比不难发现， 大写字母- 小写字母 == 32 ,
• 也就是说大写字母与小写字母在二进制表示上的只有倒数第六位（也就是表示2⁵ =>32）不一样，
• 因此我们可以通过异或 32 来快速的转换大小写字母

大写字母的 2⁵ 位原本是1 ，1^1 => 0 ， 相当于 减去了2⁵ 也就是32 ，得到小写字母

784. 字母大小写全排列

难度中等399

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出

每次执行开启一个分支（默认的分支），如果当前字符是字母，就在开启一个分支

由于先开启当前的分支 ，再改变字符数组的值，所以后续数组的改变并不会影响前面的分支，因为是前面的分支执行完了，才会执行后面的分支。

• 由于String.charAt( i )会判断 是否越界，因此实际上将String转换为字符数组，速度会更快

class Solution {
    List<String> res=new ArrayList<>();
    public List<String> letterCasePermutation(String S) {
        char[] charArray = S.toCharArray();
        myDfs(charArray, 0);
        return res;
    }
    void myDfs(char[]charArray,int index){
        if(index==charArray.length){
            res.add(new String(charArray));
            return ;
        }
        myDfs(charArray, index+1); // 开启当前的分支 
        if(Character.isLetter(charArray[index])) // 如果是 字母就开启下一个分支
        {
            charArray[index]^=32; 
            // 转换成 大写 or 小写字母 ，取决于当前的字母是大写还是小写
            myDfs(charArray, index+1);
        }
    }
}

👉知识拓展:

代码随想录 (programmercarl.com)

1️⃣回溯法解决的问题

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

组合是不强调元素顺序的，排列是强调元素顺序。

例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

2️⃣如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。

3️⃣模板

回溯三部曲

• 回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下：

void backtracking(参数)

• 回溯函数终止条件

既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

• 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

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

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

这份模板很重要，后面做回溯法的题目都靠它了！

如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。