LeetCode: 216.组合总和III
216. 组合总和 III - 力扣（LeetCode）
1.思路
结果集收集每个结果，被函数调用需要声明全局变量result和path。
递归法进行广度和深度遍历，深度遍历k层，广度遍历受限于9的数值。传递参数startIndex用以记录每层递归开始的位置。另外，三个参数的传递更方便。
2.代码实现
1// 传入四个参数 2class Solution { 3 List<List<Integer>> result = new ArrayList<>(); // 收集结果的集合 4 LinkedList<Integer> path = new LinkedList<>(); // 收集结果集 5 public List<List<Integer>> combinationSum3(int k, int n) { 6 backtracking(k, n, 1, 0); 7 return result; 8 } 9 10 public void backtracking(int k, int n, int startIndex, int sum) { 11 // sum 大于 n 时，剪枝操作return 12 if (sum > n) { 13 return; 14 } 15 // 长度大于 k 时， 剪枝操作return 16 if (path.size() > k) { 17 return; 18 } 19 // 当长度和总和均满足要求，则将path加入结果集中 20 if (sum == n && path.size() == k) { 21 result.add(new ArrayList<>(path)); 22 return; 23 } 24 // for循环进行深度和广度的遍历 25 for (int i = startIndex; i <= 9; i++) { 26 sum += i; 27 path.add(i); 28 backtracking(k, n, i + 1, sum); 29 sum -= i; // 回溯剪枝 30 path.removeLast(); // 回溯剪枝 31 } 32 } 33} 34 35// 传入三个参数可能更容易想到 36class Solution { 37 List<List<Integer>> result = new ArrayList<>(); // 收集结果的集合 38 LinkedList<Integer> path = new LinkedList<>(); // 收集结果集 39 public List<List<Integer>> combinationSum3(int k, int n) { 40 backtracking(k, n, 1); 41 return result; 42 } 43 44 public void backtracking(int k, int n, int startIndex) { 45 // sum 大于 n 时，剪枝操作return 46 if (n < 0 ) { 47 return; 48 } 49 // 长度大于 k 时， 剪枝操作return 50 if (path.size() > k) { 51 return; 52 } 53 // 当长度和总和均满足要求，则将path加入结果集中 54 if (0 == n && path.size() == k) { 55 result.add(new ArrayList<>(path)); 56 return; 57 } 58 // for循环进行深度和广度的遍历 59 for (int i = startIndex; i <= 9; i++) { 60 n -= i; 61 path.add(i); 62 backtracking(k, n, i + 1); 63 n += i; // 回溯剪枝 64 path.removeLast(); // 回溯剪枝 65 } 66 } 67}
3.复杂度分析
时间复杂度：O(n*n^2).一次递归查值（深度）对应k次递归和k次for循环，则时间消耗为n^2,n次遍历（广度）则需要n.
空间复杂度：O(k).空间复杂度取决于栈和堆空间的消耗，栈时是递归函数调用的层数k,数组则为O(k).
LeetCode: 17.电话号码的字母组合
1.思路
题意：在一个集合中，选取符合条件的两个元素可能的组合结果。
map映射映或者二维数组均可以存储相应的元素，回溯函数传入需要的参数：digits/numString/num对其进行递归即可.
2.代码实现
1class Solution { 2 3 List<String> list = new ArrayList<>(); // 存储最终结果的列表 4 StringBuilder temp = new StringBuilder(); // 创建字符串？？？ 5 6 public List<String> letterCombinations(String digits) { 7 if (digits == null || digits.length() == 0) { // 数字字符串为空或长度为0 时直接返回 8 return list; 9 } 10 String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 为每个数字对应的字母构建字符数组 11 backTracking(digits, numString, 0); // 递归函数，传入数字字符串digits，字符数组numString, 以及遍历开始位置 12 return list; 13 14 } 15 // 回溯函数 16 public void backTracking(String digits, String[] numString, int num) { 17 // 遍历长度num 等于 数字字符串dights的长度时，将结果转化为字符数组加入list中即可 18 if (num == digits.length()) { 19 list.add(temp.toString()); // 将对象temp转化为字符串表示形式 20 return; 21 } 22 String str = numString[digits.charAt(num) - '0']; // 获取当前数字对应的字母表 23 for (int i = 0; i < str.length(); i++) { // 遍历字母表中的每个字母 24 temp.append(str.charAt(i)); // 将当前字母加入到临时字符串 25 backTracking(digits, numString, num + 1); // 递归调用下一个数字的回溯 26 temp.deleteCharAt(temp.length() - 1); // 递归符合条件之后，删除临时字符串的最后一个字母，进行下一个字母的调用 27 } 28 } 29}
3.复杂度分析
时间复杂度：O(n*2^k).
空间复杂度：O(k+m).k为递归函数的深度或层数，k为字符数组的大小.
