day33——回溯专题

Bertha 。 2024-03-31 09:18 81阅读 0赞

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

*   *   *   *  回溯法介绍
             *  回溯模板
             *  回溯三部曲
             *  1.组合
             *  2.组合总和III
             *  3.电话号码的字母组合

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

##### 回溯法介绍 #####

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法解决问题

回溯法，一般可以解决如下几种问题：

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

##### 回溯模板 #####

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

##### 回溯三部曲 #####

*  递归函数的返回值以及参数
 *  回溯函数终止条件
 *  单层搜索的过程

##### 1.组合 #####

[力扣题目链接][Link 1]

class Solution {
        
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combine(int n, int k) {
        
            dfs(n,k,1);
            return result;
        }
        public void dfs(int n,int k,int startIndex){
        
            //终止条件
            if(path.size()==k){
        
                result.add(new ArrayList<>(path));
                return;
            }
            //单层逻辑
            for(int i = startIndex; i <= n - (k - path.size()) + 1;i++){
        
                path.add(i);
                dfs(n,k,i+1);
                path.removeLast();
            }
        }
    }

##### 2.组合总和III #####

[力扣题目链接][Link 2]

**思路**：

**k控制树的深度**–递归的深度

**n控制树的宽度**–for循环的范围

**代码实现**：

class Solution {
        
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            dfs(n,k,0,1);
            return result;
        }
        public void dfs(int targetSum,int k,int sum,int startIndex){
        
            //剪枝
            if(sum>targetSum){
        
                return;
            }
            //终止条件
            if(path.size()==k){
        
                if(sum==targetSum) result.add(new ArrayList<>(path));
                return; 
            }
            //单层逻辑
            for(int i = startIndex; i <= 9 - (k - path.size()) + 1;i++){
        
                sum+=i;
                path.add(i);
                dfs(targetSum,k,sum,i+1);
                sum-=i;
                path.removeLast();
            }
        }
    }

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

[力扣题目链接][Link 3]

**思路**：

1.先用数组把字符串和数字做映射

2.根据输入的数字判断其字符串

3.做拼接，做回溯

**回溯三部曲**：

*  确定回溯函数参数

参数指定是有题目中给的string digits，然后还要有二个参数就是int型的num，String型的numString

*  确定终止条件

if(num==digits.length()){
        
                list.add(temp.toString());
                return;
            }

*  确定单层遍历逻辑

String str = numString[digits.charAt(num)-'0'];
            for(int i =0;i<str.length();i++){
        
                temp.append(str.charAt(i));
                dfs(digits,numString,num+1);
                temp.deleteCharAt(temp.length()-1);

**补充**：

例如’23’，2代表"abc"

则树型结构的宽度为3

树形结构的深度为2

num为0，则str代表2对应的abc

**代码实现**：

class Solution {
        
    
        //设置全局列表存储最后的结果
        List<String> list = new ArrayList<>();
    
        public List<String> letterCombinations(String digits) {
        
            if (digits == null || digits.length() == 0) {
        
                return list;
            }
            //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
            String[] numString = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            //迭代处理
            dfs(digits, numString, 0);
            return list;
    
        }
    
        //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
        StringBuilder temp = new StringBuilder();
    
        //比如digits如果为"23",num（代表当前数组字符串的下标索引） 为0，则str表示2对应的 abc
        public void dfs(String digits, String[] numString, int num) {
        
            //遍历全部一次记录一次得到的字符串
            if (num == digits.length()) {
        
                list.add(temp.toString());
                return;
            }
            //str 表示当前num对应的字符串
            String str = numString[digits.charAt(num) - '0'];
            for (int i = 0; i < str.length(); i++) {
        
                temp.append(str.charAt(i));
                dfs(digits, numString, num + 1);
                //剔除末尾的继续尝试
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/combinations/
[Link 2]: https://leetcode.cn/problems/combination-sum-iii/
[Link 3]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/