【代码随想录训练营】【Day25】第七章｜回溯算法 ｜216.组合总和III｜17.电话号码的字母组合

组合总和III

题目详细：LeetCode.216

做过上一题组合后，再来写这道题就显得得心应手了，通过理解回溯算法的模版，也总结出了算法中的一些特点：

• 回溯算法与递归算法类似，同样需要参数、结束条件和主体逻辑
• 回溯算法我们可以将它看作是一棵二叉树，树丛根节点到叶子节点的一条路径，就是一个结果：
  • 结束条件就相当于遇到了叶子节点，保存当前路径，返回上一层
  • for循环相当于是一个选择结构，因为每个数字最多使用一次
  • 同时for循环的次数也决定了树的宽度
  • 递归的次数就相当于是for循环的嵌套次数，决定了树的深度
  • 每一次递归结束后，都要对结果进行回溯，相当于从叶子节点退回上一个节点，然后继续循环，进入下一条路径，寻找另一个结果
• 从上述回溯过程，我们也可以发现，回溯法类似对树进行深度优先遍历，找出所有的路径，保存符合预期结果的路径，所以本质上也是一种暴力法。

Java解法（回溯，递归）：

class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public void backtracking(int k, int n, int sum, int startNum){// 结束条件，叶子节点if(path.size() == k && sum == n){this.ans.add(new ArrayList<>(path));return;}// for循环，选择节点for(int i = startNum; i <= 9; i++){this.path.offer(i);sum += i;// 递归，深度优先遍历backtracking(k, n, sum, i + 1);// 回溯，返回叶子节点的上一节点this.path.removeLast();sum -= i;// 继续循环，进入其他节点，寻找符合结果的路径}}public List<List<Integer>> combinationSum3(int k, int n) {this.backtracking(k, n, 0, 1);return this.ans;}
}

---

电话号码的字母组合

题目详细：LeetCode.17

这道题我一开始的思路和前两道练习搞混了，琢磨了一个钟之后，看了题解才恍然大悟，原来这道题的不同点是在于在不同集合中找组合。

详细的解释可以看题解：《代码随想录—电话号码的字母组合》

Java解法（递归， 回溯）：

class Solution {public List<String> ans = new ArrayList<>();public StringBuffer path = new StringBuffer();public char[][] mapper_all = {{'a','b','c'},{'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};public List<String> letterCombinations(String digits) {this.backtracking(digits, 0);return this.ans;}public void backtracking(String digits, int startNum){if(path.length() == digits.length()){if(path.length() != 0){ans.add(path.toString());}return;}char[] mapper = mapper_all[digits.charAt(startNum) - '0' - 2];for(int i = 0; i < mapper.length; i++){this.path.append(mapper[i]);// 递归，注意startNum + 1，表示要处理下一个数字了backtracking(digits, startNum + 1);this.path.deleteCharAt(path.length() - 1);}}
}

注意这里for循环，可不像前两天的练习（LeetCode.77和.216）中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而之前的练习（LeetCode.77和.216）是求同一个集合中的组合！

---