java-代码随想录第22天| 回溯算法理论基础、77.组合、216.组合总和III、17.电话号码的字母组合

qq_57465625

619人浏览 · 2025-09-03 11:28:32

qq_57465625 · 2025-09-03 11:28:32 发布

参考链接：代码随想录

回溯算法理论基础

什么是回溯法

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

回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。

回溯法的效率

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

为什么还要用它呢？

没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题

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

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

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

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

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

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

回溯法模板

1.回溯函数模板返回值以及参数

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

2.回溯函数终止条件

3.回溯搜索的遍历过程

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

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

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

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

组合问题

图中可以发现n相当于树的宽度，k相当于树的深度。只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

77.组合

链接：77. 组合 - 力扣（LeetCode）

题目：

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

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

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;  
    }
    public 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);            //选择当前数字i
            backtracking(n,k,i+1);  //递归：从i+1开始选取下一个数字
            path.removeLast();      //回溯：撤销选择，尝试其他分支
        }
    }
}

216.组合总和III

链接：216. 组合总和 III - 力扣（LeetCode）

题目：

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

只使用数字1到9

每个数字 最多使用一次

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

class Solution {
    LinkedList<Integer> path=new LinkedList<>();
    List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        build(k,n,1,0);
        return ans;
    }
    private void build(int k,int n,int startIndex,int sum){
        //剪枝
        if(sum > n) return;
        if(path.size() > k) return;

        if(sum == n && path.size()==k){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<=9;i++){
            //确定本层第一个元素
            path.add(i);
            sum+=i;
            //递归：确定本层其他元素
            build(k,n,i+1,sum);
            sum-=i;
            //回溯，撤销处理结果
            path.removeLast();
        }
    }
}

17.电话号码的字母组合

链接：17. 电话号码的字母组合 - 力扣（LeetCode）

题目:

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

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

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"};
        //迭代处理
        backTracking(digits, numString, 0);
        return list;

    }
    //每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(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));
            //递归，处理下一层
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }

}