代码学习记录21--回溯算法第二天

随想录日记part21

$time：$ 2024.03.16

主要内容：今天主要是结合类型的题目加深对回溯算法的理解：1：组合总和；2：电话号码的字母组合

• 216.组合总和III
• 17.电话号码的字母组合

Topic1组合总和

题目：

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

• 只使用数字 $1$ 到 $9$
• 每个数字最多使用一次

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

输入： $k=3,n=9$
输出： $[[1,2,6],[1,3,5],[2,3,4]]$
解释：
$1+2+6=9$
$1+3+5=9$
$2+3+4=9$
没有其他符合的组合了。

思路： 按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量，$path$用来存放符合条件单一结果，$result$用来存放符合条件结果的集合。回溯函数里一定有两个参数，既然是集合 $[1,9]$ 里面取 $k$ 个数和为 $n$，所以需要 $n$ 和$k$ 是两个 $int$ 的参数。还需要一个参数为 $int$ 型变量 $startIndex$，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是 $[1,...,n]$ ）。
所以整体代码如下：

List<List<Integer>> result=new ArrayList<>();
LinkedList<Integer> path=new LinkedList<>();
private void backtracking(int n,int k, int statindex){}

2.回溯函数终止条件
回溯出口，如果 $path$ 里面的数量等于 $K$，说明其到达叶子节点，若 $path$ 中所有元素之和为$n$，则将其加入到 $result$，否则直接返回 $return$
代码如下：

if (k == path.size()) {// 回溯出口，如果Path里面的数量等于K，说明其到达叶子节点
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += path.get(i);
            }
            if (sum == targetSum)
                result.add(new ArrayList<>(path));
            return;// 如果path.size() == k 但sum != targetSum 直接返回
        }

3.回溯搜索的遍历过程
$for$ 循环每次从 $startIndex$ 开始遍历，然后用 $path$ 保存取到的节点i搜索的过程如下图：

实现代码如下：

for (int i = startindex; i <= 9; i++) {
            path.add(i);
            backtracking(targetSum, k, i + 1);
            path.removeLast();
        }

完整的代码如下：

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放结果集合
    LinkedList<Integer> path = new LinkedList<>();// 存放一个满足条件的路径
    public List<List<Integer>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtracking(n, k, 1);
        return result;
    }
    // targetSum：目标和，也就是题目中的n。
    // k：题目中要求k个数的集合。
    // startIndex：下一层for循环搜索的起始位置。
    private void backtracking(int targetSum, int k, int startindex) {
        if (k == path.size()) {// 回溯出口，如果Path里面的数量等于K，说明其到达叶子节点
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += path.get(i);
            }
            if (sum == targetSum)
                result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startindex; i <= 9; i++) {
            path.add(i);
            // sum += i;
            backtracking(targetSum, k, i + 1);
            // sum -= i;
            path.removeLast();
        }
    }

}

Topic2电话号码的字母组合

题目：

给定一个仅包含数字 $2$-$9$ 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 $1$ 不对应任何字母。

输入： $digits="23"$
输出： $["ad","ae","af","bd","be","bf","cd","ce","cf"]$

思路： 按照回溯模板我们进行回溯三部曲：
递归三部曲：

1.回溯函数模板返回值以及参数
在这里要定义两个全局变量，$temp$用来存放符合条件单一结果，$list$用来存放符合条件结果的集合，与此同时我们需要建立一个数字到字符的映射，我们使用字符串数组 $numString$ 表示，还需要一个记录查到第几个第几个字符的索引 $startindex$
所以整体代码如下：

// 设置全局列表存储最后的结果
List<String> list = new ArrayList<>();
// 每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的     
StringBuild StringBuilder temp = new StringBuilder();
void backtracking(String digits, String[] numString, int startindex)

2.回溯函数终止条件
回溯出口，如果索引值 $startindex$ 里面的数量等于 $digits.length()$，说明其到达叶子节点，则将$temp$其加入到 $list$，否则直接返回 $return$
代码如下：

if (startindex == digits.length()) {// 查完最后一个字符，到达回溯出口
	list.add(temp.toString());
    return;
}

3.回溯搜索的遍历过程
$for$ 循环每次从 $startIndex$ 开始遍历，然后用 $temp$ 保存取到的节点i搜索的过程如下图：

实现代码如下：

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

完整的代码如下：

class Solution {
    List<String> list = new ArrayList<>();// 设置全局列表存储最后的结果
    // 每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();
    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;
    }

    private void backtracking(String digits, String[] numString, int startindex) {
        if (startindex == digits.length()) {// 查完最后一个字符，到达回溯出口
            list.add(temp.toString());
            return;
        }
        // 得到digits[startindex]映射的字符串
        String str = numString[digits.charAt(startindex) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            backtracking(digits, numString, startindex + 1);
            temp.deleteCharAt(temp.length() - 1);      
        }
    }
}

时间复杂度: $O(3^m\ast 4^n)$，其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数
空间复杂度: $O(3^m\ast 4^n)$