zj

前言

今天开始学习回溯算法啦，虽然直接递归学习的时候有涉及到回溯但是没有系统性的学习，希望博主记录的内容能够对大家有所帮助，一起加油吧朋友们！💪💪💪

组合

LeetCode题目链接

给定一个整数n和一个整数k，要求返回[1, n]中所有可能的k个数的组合

1728740308724

首先的话需要知道组合的特点是顺序不重要，这启示我们可以用列表来存🤔🤔🤔

我们来梳理逻辑

回溯法的核心是用递归来构建每一个可能的组合，通过递归遍历所有可能的数并在选择时跳过已经选择过的数字🤔，所以我们可以定义一个结果列表result，一个组合列表path，一个数字索引startIndex，每层往下数字索引递增，选择数字加入path，当path的长度等于k则把组合加入结果集，递归完成后回溯path来存储其他组合😲

我们来进一步梳理回溯三要素

递归函数的参数和返回值

//把结果集和组合定义为全局变量，避免太多参数导致递归处理不好理解
List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合 List<Integer> path = new ArrayList<>();//存放符合条件的结果

//递归处理无返回值，递归完result已经填充完毕，n为数的最大值，k为组合大小，在递归处理中需要
private void backtracking(int n, int k, int startIndex){}

回溯函数终止条件（这里要生成path副本来存入结果集中，如果存path的话只是一个引用，path回溯撤销时，result中的元素也将同时撤销🤔🤔🤔）

if(path.size() == k){ //终止条件:组合长度等于k
    result.add(new ArrayList<>(path));//存放结果
    return;
}

单层搜索过程(这里是包含未剪枝处理的搜索逻辑与剪枝的搜索逻辑，因为有些不必要的搜索可以剪掉🤔🤔🤔，剪掉这些搜索就称为剪枝，这里剪枝是因为要组合长度为k，然后如果数字索引到后面总的搜索次数都不够添加k个元素形成一个组合那就没有必要搜索了🤔🤔🤔)

for(int i = startIndex; i <= n; i++){//选择本层集合中的元素
    path.add(i);//处理节点
    backtracking(n, k, i + 1);//递归
    path.removeLast();//回溯撤销处理的节点
}
for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){//选择本层集合中的元素
    path.add(i);//处理节点
    backtracking(n, k, i + 1);//递归
    path.removeLast();//回溯撤销处理的节点
}

回溯的完整代码如下

//未剪枝
// class Solution {
//     List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合
//     List<Integer> path = new ArrayList<>();//存放符合条件的结果
//     public List<List<Integer>> combine(int n, int k) {
//         backtracking(n, k, 1);
//         return result;
//     }

//     private void backtracking(int n, int k, int startIndex){
//         if(path.size() == k){ //终止条件
//             result.add(new ArrayList<>(path));//存放结果
//             return;
//         }
        // for(int i = startIndex; i <= n; i++){//选择本层集合中的元素
        //     path.add(i);//处理节点
        //     backtracking(n, k, i + 1);//递归
        //     path.removeLast();//回溯撤销处理的节点
        // }
//     }
// }

//剪枝
class Solution {
    List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合
    List<Integer> path = new ArrayList<>();//存放符合条件的结果
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int startIndex){ //可剪枝处
        if(path.size() == k){ //终止条件
            result.add(new ArrayList<>(path));//存放结果
            return;
        }
        /**
        如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数那就没有必要搜索了
        已经选择的元素path.size()
        还需要选择的元素k - path.size()
        在集合中至多要从n - (k - path.size()) + 1开始遍历
         */
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){//选择本层集合中的元素
            path.add(i);//处理节点
            backtracking(n, k, i + 1);//递归
            path.removeLast();//回溯撤销处理的节点
        }
    }
}

组合总和III

LeetCode题目链接

就是也是找组合，找什么组合呢？从[1,9]区间里找一个长度为k的组合，使得这个组合的数总和为n，组合中每个数只能出现一次

1728741858450

我们来梳理一下逻辑

回溯搜索的话从区间1~9取数，向组合中添加数字，累计当前的总和。在递归过程中，如果组合的长度达到了 k 且组合的和等于 n，则该组合为有效结果，加入到结果集中。如果组合长度超过 k，或者当前数字的和已经超过 n，则不需要继续递归，进行回溯。每次递归时尝试选择数字，之后在递归返回时将该数字移除（即回溯），以便尝试其他可能性🤔🤔🤔

我们来进一步梳理回溯三要素

递归函数的参数和返回值

//定义结果集和组合的全局变量，减少递归参数
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
//回溯搜索所需的数字索引、目标和n、组合长度k
private void backtracking(int k, int n, int startIndex){}

回溯终止条件

if(path.size() == k){//终止条件
    if(path.stream().mapToInt(Integer::intValue).sum() == n) result.add(new ArrayList<>(path));//如果组合的和为目标和且组合长度为目标长度则把组合副本加入结果集
    return;
}

单层搜索过程（这里大家选一种写即可，这里剪枝的话包含循环时把不够组合长度的搜索剪掉以及把组合的和大于目标和后的不必要递归也剪掉🤔🤔🤔）

//未剪枝的单层搜索过程
for(int i = startIndex; i <= 9; i++){ 
    path.add(i);
    backtracking(k, n, i + 1);
    path.removeLast();//回溯
}
//剪枝的单层搜索过程
for(int i = startIndex; i <= 9 - (k - path.size()) + 1 ; i++){//个数剪枝
    path.add(i);
    if(path.stream().mapToInt(Integer::intValue).sum() > n){//求和剪枝
        path.removeLast();//先回溯
        return;
    }
    backtracking(k, n, i + 1);
    path.removeLast();//回溯
}

回溯的完整代码如下

/**不剪枝 */
// class Solution {
//     List<List<Integer>> result = new ArrayList<>();
//     List<Integer> path = new ArrayList<>();
//     public List<List<Integer>> combinationSum3(int k, int n) {
//         backtracking(k, n, 1);
//         return result;
//     }
//     private void backtracking(int k, int n, int startIndex){
//         if(path.size() == k){//终止条件
//             if(path.stream().mapToInt(Integer::intValue).sum() == n) result.add(new ArrayList<>(path));
//             return;
//         }
        // for(int i = startIndex; i <= 9; i++){ 
        //     path.add(i);
        //     backtracking(k, n, i + 1);
        //     path.removeLast();//回溯
        // }
//     }
    
// }

/**剪枝 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }
    private void backtracking(int k, int n, int startIndex){
        if(path.size() == k){//终止条件
            if(path.stream().mapToInt(Integer::intValue).sum() == n) result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <= 9 - (k - path.size()) + 1 ; i++){//个数剪枝
            path.add(i);
            if(path.stream().mapToInt(Integer::intValue).sum() > n){//求和剪枝
                path.removeLast();//先回溯
                return;
            }
            backtracking(k, n, i + 1);
            path.removeLast();//回溯
        }
    }
    
}

电话号码的字母组合

LeetCode题目链接

这道题就是给一个字符串类似"23"，然后的话手机按键上不是像2或者3它会各自对应一组字符类似"abc"这种，然后就是把对应的字符的所有组合进行一个返回。

1728744424368

我们来梳理思路

先定义一个数字到字母的映射表（类似于电话键盘上的数字对应字母），然后使用回溯法从第一个数字开始，每次选择该数字对应的一个字母，递归进入下一个数字，继续选择字母。当递归路径达到输入字符串的长度时，说明已经生成了一个完整的字母组合，将它加入结果集中。在回溯过程中每次递归完成后回到上一步，尝试其他字母组合，直至所有组合都被遍历🤔🤔🤔

我们进一步来梳理回溯三要素

确定递归的参数和返回值

List<String> result = new ArrayList<>();
StringBuilder s = new StringBuilder();//会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
String[] map = {
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
};
private void backtracking(String digits, int index){}

回溯终止条件（数字索引等于给的数字字符串长度时把字母组合加入到结果集中🤔）

if(index == digits.length()){ //出口
    result.add(s.toString());
    return;
}

单层搜索过程

String str = map[digits.charAt(index) - '0'];//先根据数字索引找对应的可用字母
for(int i = 0; i < str.length(); i++){//递归进行字母组合
    s.append(str.charAt(i));
    backtracking(digits, index + 1);
    s.deleteCharAt(s.length() - 1);
}

完整的回溯代码如下：

class Solution {
    List<String> result = new ArrayList<>();
    StringBuilder s = new StringBuilder();//会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    String[] map = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0)return result;
        backtracking(digits, 0);
        return result;
    }

    private void backtracking(String digits, int index){ //index是用来遍历digits的
        if(index == digits.length()){ //出口
            result.add(s.toString());
            return;
        }
        String str = map[digits.charAt(index) - '0'];
        for(int i = 0; i < str.length(); i++){
            s.append(str.charAt(i));
            backtracking(digits, index + 1);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

总结

今天的回溯学习就到这里啦，继续加油，奥利给✊✊✊

前言

组合

组合总和III

电话号码的字母组合

总结

Copyright © 2020 | Author: 周建 | Theme By Coder