【随想录】Day25—第七章回溯算法part02

本文主要是介绍【随想录】Day25—第七章回溯算法part02，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1: 组合总和 III

题目链接：216. 组合总和 III

1- 思路

借助 path 和 res 数据结构收集结果
回溯三部曲

1. 回溯参数及返回值
1. 回溯终止条件 && 结果收集
1. for 循环回溯逻辑

2- 题解

⭐ 组合总和 III ——题解思路

在这里插入图片描述

class Solution {public List<List<Integer>> combinationSum3(int k, int n) {backTracing(k, n, 1);return res;}int nowSum = 0;List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public void backTracing(int k, int n, int startIndex) {// 终止条件if (path.size() == k && nowSum == n) {res.add(new ArrayList(path));return;}for (int i = startIndex; i <= 9; i++) {nowSum += i;path.add(i);backTracing(k, n, i + 1);nowSum -= i;path.removeLast();}}
}

题目2: 电话号码的字母组合

题目链接：17. 电话号码的字母组合

1- 思路

回溯树的

深度是由输入数字的个数来决定的
树的宽度是由每次递归的 str 实现的

回溯三部曲

1. 回溯参数及返回值
- **digits**：记录输入的字符串
- **numToStr**：哈希表，存储数字到字母的映射关系
- **index**：记录当前 digits 遍历到的位置
2. 递归终止条件
- 本题通过 index 记录 digits 遍历的位置，即 digits 遍历完成则完成了这个过程
3. 递归逻辑
- 由于树的宽由每次数字映射的字符串所决定，所以每层递归过程中，重新获取 numToStr 的长度，从而 for 遍历的就是 str 的长度
- 利用 sb 收集当前字符串
- 单层递归调用 backTracing(digits,numToStr,index+1)
- 之后回溯：sb移除最后一个元素

2- 题解

⭐ 电话号码的字母组合 ——题解思路

在这里插入图片描述

class Solution {List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits==null || digits.length()==0){return res;}String[] numToStr = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backTracing(digits,numToStr,0);return res;}StringBuilder sb = new StringBuilder();public void backTracing(String digits,String[] numToStr,int index){// 终止条件if(index == digits.length()){res.add(sb.toString());return;}// 回溯 for 收集 sbString str = numToStr[digits.charAt(index)-'0'];for(int i = 0;i<str.length();i++){sb.append(str.charAt(i));backTracing(digits,numToStr,index+1);sb.deleteCharAt(sb.length()-1);}}}