本文主要是介绍代码随想录算法训练营第二十五天| LeetCode216. 组合III、LeetCode17.电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#LeetCode 216. Combination III
#LeetCode 216. 视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
如果做了77 题后，这个题目可以用相似的思路。回溯三部曲：
1. 确定递归函数的参数以及返回值：一维数组path来存放符合条件的结果，二维数组result来存放结果集。
2. 确定终止条件：path 的长度等于目标长度k 。
3. 确定单层递归逻辑：path 收集每次选取的元素，用sum来记录path 里元素的和。
代码：
class Solution {LinkedList path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 1, 0);return result;}public void backtracking(int k, int n, int startIndex, int sum) {if (sum > n) {return;}if (sum == n) {if (path.size() == k) {result.add(new LinkedList<>(path));}return;}for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {path.add(i);sum += i;backtracking(k, n, i + 1, sum);sum -= i;path.removeLast();}}
}#LeetCode 17. Letter Combinations of a Phone Number
#LeetCode 17. 视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
这个遇上一个题目index 的区别是，上一个题目的index 是为了记录不同的起始位置，来保证生成不同的结果，这个题目是在两个字符串中操作，所以i 都是在0 开始。
这个题目中的index 是记录遍历到digits 中的第几个数字了。终止条件就是如果index 等于输入的数字个数，注意这里是length 不是length - 1 ，因为最后一个元素也会被操作。StringBuilder 在java 中有很多常用方法，例如：append(), deleteCharAt(), insert()等。
代码：
class Solution {StringBuilder path = new StringBuilder();List<String> result = new ArrayList<>();public List<String> letterCombinations(String digits) {if (digits.length() == 0 || digits == null) {return result;}String[] letterMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtracking(digits, letterMap, 0);return result;}public void backtracking(String digits, String[] letterMap, int index) {if (digits.length() == index) {result.add(path.toString());return;}int digit = digits.charAt(index) - '0';String letter = letterMap[digit];for (int i = 0; i < letter.length(); i++) {path.append(letter.charAt(i));backtracking(digits, letterMap, index + 1);path.deleteCharAt(path.length() - 1);}}
}这篇关于代码随想录算法训练营第二十五天| LeetCode216. 组合III、LeetCode17.电话号码的字母组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
