LeetCode 热题 HOT 100：回溯专题

短命女 2023-10-16 16:54 25阅读 0赞

LeetCode 热题 HOT 100：[https://leetcode.cn/problem-list/2cktkvj/][https_leetcode.cn_problem-list_2cktkvj]

--------------------

#### 文章目录 ####

*   *  17. 电话号码的字母组合
     *  22. 括号生成
     *  39. 组合总和
     *  46. 全排列
     *  补充：47. 全排列 II （待优化)
     *  78. 子集
     *  79. 单词搜索
     *  124. 二叉树中的最大路径和
     *  200. 岛屿数量
     *  437. 路径总和 III

--------------------

### 17. 电话号码的字母组合 ###

题目链接：[https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_letter-combinations-of-a-phone-number_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        List<String> list;
        Map<Character, String> map;
    
        public List<String> letterCombinations(String digits) {
        
            ap = new HashMap<>();
            res = new LinkedList<>();
            if(digits.length() == 0){
        
                return res;
            }
            map.put('2', "abc");
            map.put('3', "def");
            map.put('4', "ghi");
            map.put('5', "jkl");
            map.put('6', "mno");
            map.put('7', "pqrs");
            map.put('8', "tuv");
            map.put('9', "wxyz");
            backTrack(digits, 0, new StringBuilder());
            return list;
        }
    
        public void backTrack(String digits, int ind, StringBuilder sb){
         // 参数：输入的字符串、字符串的索引、拼接的英文字符串
            if(digits.length() == ind){
        
                list.add(sb.toString());
            }else{
        
                char ch = digits.charAt(ind);
                String str = map.get(ch); // 获取按键下面的字符序列
                for (int i = 0; i < str.length(); i++) {
        
                    sb.append(str.charAt(i));
                    backTrack(digits, ind + 1, sb);
                    sb.deleteCharAt(sb.length()-1); // 回溯
                }
            }
        }
    }

参考题解：[https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_letter-combinations-of-a-phone-number_solutions_388738_dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

![在这里插入图片描述][688be99a1d47420c8914fe3b3f191b1e.png]

--------------------

### 22. 括号生成 ###

题目链接：[https://leetcode.cn/problems/generate-parentheses/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_generate-parentheses_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

思路一：

class Solution {
        
        List<String> res;
        public List<String> generateParenthesis(int n) {
        
            res = new LinkedList<>();
            backTrack(n, 0, 0, "");
            return res;
        }
    
        public void backTrack(int n, int left, int right, String str){
        
            if(left < right){
        
                return;
            }
            if(left == n && right == n){
        
                res.add(str);
                return;
            }else{
        
                if(left < n){
        
                    backTrack(n, left+1, right, str+"(");
                }
                backTrack(n, left, right+1, str+")");
            }
        }
    }

思路二：

class Solution {
        
        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
        
            if(n<=0){
        
                return res;
            }
            getBracket("", n, n);
            return res;
        }
    
        public void getBracket(String str, int left, int right){
        
            if(left == 0 && right == 0){
        
                res.add(str);
                return;
            }
            if(left == right){
        
                getBracket(str+"(", left-1, right);
            }else{
        
                if(left > 0){
        
                    getBracket(str+"(", left-1, right);
                }
                getBracket(str+")", left, right-1);
            }
        }
    }

--------------------

### 39. 组合总和 ###

题目链接：[https://leetcode.cn/problems/combination-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_combination-sum_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
    
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            dfs(candidates, target, 0);
            return res;
        }
    
        public void dfs(int[] candidates, int target, int ind){
         // 关键点在于索引
            if(target == 0){
        
                res.add(new ArrayList<>(list));
                return;
            }
    
            for(int i = ind; i < candidates.length; i ++){
        
                if(target - candidates[i] >= 0){
        
                    list.add(candidates[i]);
                    dfs(candidates, target - candidates[i], i); 
    			    // 每次在当前的索引上进行遍历，作用在于：如果没有索引：target=5，5-3-2 作用等同于 5-2-3, 那么会有两种组合[2,3]与[3,2]
                    // 但是在索引的约束下，不会出现这种情况 
                    list.remove(list.size()-1);
                }
            }
        }
    }

参考链接：[https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_combination-sum_solutions_14697_hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]  
![在这里插入图片描述][96abca0c1f6a4000b3faa06109a891f9.png_pic_left]

--------------------

### 46. 全排列 ###

题目链接：[https://leetcode.cn/problems/permutations/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_permutations_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
    
        public List<List<Integer>> permute(int[] nums) {
        
            boolean[] visited = new boolean[nums.length]; // 标志数组
            dfs(nums, 0, visited);
            return res;
        }
    
        public void dfs(int[] nums, int size, boolean[] visited){
        
            if(size == nums.length){
        
                res.add(new ArrayList<>(list));
                return;
            }
            for(int i = 0; i < nums.length; i ++){
        
                if(!visited[i]){
        
                    visited[i] = true;
                    list.add(nums[i]);
                    dfs(nums, size+1, visited);
                    list.remove(list.size()-1); // 回溯
                    visited[i] = false;
                }
            }
        }
    }

参考链接：[https://leetcode.cn/problems/permutations/solutions/9914/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_permutations_solutions_9914_hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

![在这里插入图片描述][afd4def474ae418c9c6ea1f7d1cfd450.png_pic_left]

--------------------

### 补充：47. 全排列 II （待优化) ###

题目链接：[https://leetcode.cn/problems/permutations-ii/description/?envType=featured-list&envId=2cktkvj%3FenvType%3Dfeatured-list&envId=2cktkvj][https_leetcode.cn_problems_permutations-ii_description_envType_featured-list_envId_2cktkvj_3FenvType_3Dfeatured-list_envId_2cktkvj]

class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
    
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            boolean[] visited = new boolean[nums.length]; // 标志数组
            dfs(nums, 0, visited);
            return res;
        }
    
        public void dfs(int[] nums, int size, boolean[] visited){
        
            if(size == nums.length){
        
                for (List<Integer> result : res) {
        
                    if(result.equals(list)){
        
                        return;
                    }
                }
                res.add(new ArrayList<>(list));
                return;
            }
            for(int i = 0; i < nums.length; i ++){
        
                if(!visited[i]){
        
                    visited[i] = true;
                    list.add(nums[i]);
                    dfs(nums, size+1, visited);
                    list.remove(list.size()-1);
                    visited[i] = false;
                }
            }
        }
    }

--------------------

### 78. 子集 ###

题目链接：[https://leetcode.cn/problems/subsets/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_subsets_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
    
        public List<List<Integer>> subsets(int[] nums) {
        
            dfs(nums, 0);
            return res;
        }
    
        public void dfs(int[] nums, int i){
        
            if(i==nums.length){
        
                res.add(new ArrayList(list));
                return;
            }
            // 选 nums[i]
            list.add(nums[i]);
            dfs(nums, i+1);
            // 不选 nums[i]
            list.remove(list.size()-1);
            dfs(nums, i+1);
        }
    }

![在这里插入图片描述][0087a53f1a0748dcbc7cf8c547132e19.png_pic_left]

--------------------

### 79. 单词搜索 ###

题目链接：[https://leetcode.cn/problems/word-search/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_word-search_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
    
        public boolean exist(char[][] board, String word) {
        
            for(int i = 0; i < board.length; i ++){
        
                for(int j = 0; j < board[0].length; j ++){
        
                    if(board[i][j] == word.charAt(0)){
        
                        if(dfs(board, i, j, word, 0)){
         // 路径开头不一定只有一处，所以要遍历整个数组
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    
        public boolean dfs(char[][] board, int i, int j, String word, int ind){
        
            if(ind >= word.length()){
        
                return true;
            }
            if(i>=0 && i<board.length && j>=0 && j<board[0].length && board[i][j]==word.charAt(ind) && board[i][j]!='\0'){
         // 剪枝
                char tmp = board[i][j];
                board[i][j] = '\0'; // 设置不可访问
                boolean f1 = dfs(board, i, j-1, word, ind+1); // 左
                boolean f2 = dfs(board, i-1, j, word, ind+1); // 上
                boolean f3 = dfs(board, i, j+1, word, ind+1); // 右
                boolean f4 = dfs(board, i+1, j, word, ind+1); // 下
                board[i][j] = tmp; // 回溯
                return f1 || f2 || f3 ||f4;
            }
            return false;
        }
    }

--------------------

### 124. 二叉树中的最大路径和 ###

题目链接：[https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_binary-tree-maximum-path-sum_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

*  二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。最大的路径，可能的路径情况：  
      `a`  
     `/ \`  
    `b c`  
    ① b + a + c。  
    ② b + a + a 的父结点。（需要再次递归）  
    ③ a + c + a 的父结点。（需要再次递归）
 *  其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和，因此可以在递归过程中通过比较得出。
 *  情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解。

class Solution {
        
        int max = Integer.MIN_VALUE;
    
        public int maxPathSum(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            dfs(root);
            return max;
        }
    
        /**
         * 返回经过root的单边分支最大和， 即 Math.max(root, root+left, root+right)
         */
        public int dfs(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            // 计算左子树最大值，左边分支如果为负数还不如不选择
            int leftMax = Math.max(0, dfs(root.left));
            // 计算右子树最大值，右边分支如果为负数还不如不选择
            int rightMax = Math.max(0, dfs(root.right));
    
            // left->root->right 作为路径与已经计算过历史最大值做比较
            max = Math.max(max, leftMax + root.val + rightMax);
    
            // 返回经过root的单边最大分支给当前root的父节点计算使用
            return root.val + Math.max(leftMax, rightMax);
        }
    }

--------------------

### 200. 岛屿数量 ###

题目链接：[https://leetcode.cn/problems/number-of-islands/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_number-of-islands_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        public int numIslands(char[][] grid) {
        
            int sum = 0;
            for(int i = 0; i < grid.length; i ++){
        
                for(int j = 0; j < grid[0].length; j ++){
        
                    if(grid[i][j] == '1'){
        
                        dfs(grid, i, j);
                        sum++;
                    }
                }
            }
            return sum;
        }
        
        public void dfs(char[][] grid, int x, int y){
        
            if(0<=x && x<grid.length && 0<=y && y<grid[0].length && grid[x][y] == '1'){
        
                grid[x][y] ='0';
                dfs(grid, x, y-1); // 左
                dfs(grid, x-1, y); // 上
                dfs(grid, x, y+1); // 右
                dfs(grid, x+1, y); // 下
            }
        }
    }

--------------------

### 437. 路径总和 III ###

题目链接：[https://leetcode.cn/problems/path-sum-iii/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_path-sum-iii_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        // key 是前缀和，value 是前缀和为这个值的路径数量。
        Map<Long, Integer> map = new HashMap<>();
        int target;
    
        public int pathSum(TreeNode root, int targetSum) {
        
            this.target = targetSum;
            // 可能路径从根节点开始算
            map.put(0l, 1);
            return dfs(root, 0l);
        }
    
        public int dfs(TreeNode root, long curSum){
        
            if(root == null){
        
                return 0;
            }
            curSum += root.val; // 当前累计的结点值
            int res = 0;
            // 以当前节点为止，去查看从前的 map 集合中是否还存在目标前缀和
            //              1
            //             /
            //            2
            //           /
            //          3
            // 假设目标和为 5
            // 节点 1 的前缀和为：1
            // 节点 3 的前缀和为: 1+2+3 = 6
            // pre(3) - pre(1) = 5
            // 所以从节点 1 到节点 3 之间有一条符合要求的路径
            res += map.getOrDefault(curSum-target, 0);
    
            // 存储路径的原因是可能节点的前缀和存在相等的情况：
            //              2
            //             /
            //            0
            //           /
            //          4
            // 从节点 2 到节点 4 有两条路径长度等于2
            map.put(curSum, map.getOrDefault(curSum, 0) + 1);
    
            int left = dfs(root.left, curSum); // 调用左子树
            int right = dfs(root.right, curSum); // 调用右子树
    
            res = res + left + right;
    
            map.put(curSum, map.get(curSum)-1); // 恢复状态
    
            return res;
        }
    }

--------------------

[https_leetcode.cn_problem-list_2cktkvj]: https://leetcode.cn/problem-list/2cktkvj/
[https_leetcode.cn_problems_letter-combinations-of-a-phone-number_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_letter-combinations-of-a-phone-number_solutions_388738_dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[688be99a1d47420c8914fe3b3f191b1e.png]: https://img-blog.csdnimg.cn/688be99a1d47420c8914fe3b3f191b1e.png
[https_leetcode.cn_problems_generate-parentheses_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/generate-parentheses/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_combination-sum_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/combination-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_combination-sum_solutions_14697_hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[96abca0c1f6a4000b3faa06109a891f9.png_pic_left]: https://img-blog.csdnimg.cn/96abca0c1f6a4000b3faa06109a891f9.png#pic_left
[https_leetcode.cn_problems_permutations_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/permutations/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_permutations_solutions_9914_hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/permutations/solutions/9914/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[afd4def474ae418c9c6ea1f7d1cfd450.png_pic_left]: https://img-blog.csdnimg.cn/afd4def474ae418c9c6ea1f7d1cfd450.png#pic_left
[https_leetcode.cn_problems_permutations-ii_description_envType_featured-list_envId_2cktkvj_3FenvType_3Dfeatured-list_envId_2cktkvj]: https://leetcode.cn/problems/permutations-ii/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_subsets_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/subsets/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[0087a53f1a0748dcbc7cf8c547132e19.png_pic_left]: https://img-blog.csdnimg.cn/0087a53f1a0748dcbc7cf8c547132e19.png#pic_left
[https_leetcode.cn_problems_word-search_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/word-search/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_binary-tree-maximum-path-sum_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_number-of-islands_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/number-of-islands/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_path-sum-iii_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/path-sum-iii/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj