代码随想录算法训练营第二五天

代码随想录算法训练营第二五天 | 回溯组合

本文主要是介绍代码随想录算法训练营第二五天 | 回溯组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

组合总和

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

只使用数字1到9

每个数字最多使用一次

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

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k, n, 1);return result;}private void backtracking(int k, int n, int startIndex) {if (n < 0) return;   // 剪枝if (list.size() == k) {if (n == 0) {result.add(new ArrayList<>(list)); // 容易忘记 new 一个}return;  // 如果path.size() == k 但sum != targetSum 直接返回}for (int i = startIndex; i <= 9 - (k - list.size()) + 1; i++) {  // 剪枝list.add(i);     backtracking(k, n - i, i + 1);  list.removeLast();  // 注意：处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！}}
}

		for(int i = startIndex; i <= 9; i++) {path.add(i);sum += i;build(k, n, i + 1, sum);sum -= i;path.removeLast();}

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {Map<Integer, String> hm = new HashMap<>();List<String> result = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {hm.put(2, "abc");hm.put(3, "def");hm.put(4, "ghi");hm.put(5, "jkl");hm.put(6, "mno");hm.put(7, "pqrs");hm.put(8, "tuv");hm.put(9, "wxyz");if (digits == null || digits.length() == 0) return result;backtracking(digits, 0);return result;}private void backtracking(String digits, int index) {// index 是遍历digits的if (index == digits.length()) {result.add(sb.toString());return;}String str = hm.get(digits.charAt(index) - '0'); // 当前对应的字符串for(int i = 0; i < str.length(); i++) {sb.append(str.charAt(i));backtracking(digits, index + 1);sb.deleteCharAt(sb.length() - 1);     // 注意 deleteCharAt()方法                     }}
}