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

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

---

题目1: 组合总和 III

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

---

1- 思路

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

• 1. 回溯参数及返回值
• 2. 回溯终止条件 && 结果收集
• 3. 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);}}}

这篇关于【随想录】Day25—第七章 回溯算法part02的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---