一、216.组合总和III
结束条件：一个是集合的大小达到k，另一个是和等于targetSum
循环：sum加了i，回溯的时候要减掉i。
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k, n, 0, 1);
return result;
}
private void backtracking(int k, int targetSum, int sum, int startIndex) {
if(sum > targetSum) return;
if (path.size() == k) {
if (sum == targetSum) {
result.add(new ArrayList<>(path));
}
return;
}
for(int i = startIndex; i <= 9; i++) {
sum += i;
path.add(i);
backtracking(k, targetSum, sum, i + 1);
sum -= i;
path.removeLast();
}
}
}二、17.电话号码的字母组合
理解本题后，要解决如下三个问题：
- 数字和字母如何映射
- 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
- 输入1 * #按键等等异常情况
回溯三部曲：
- 确定回溯函数参数
首先需要一个字符串temp来收集叶子节点的结果，然后用一个集合result保存起来。
再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index和numString映射表。（这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。）
- 确定终止条件
例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。
然后收集结果，结束本层递归。
- 确定单层遍历逻辑
首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。
因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合 (opens new window)和216.组合总和III (opens new window)都是是求同一个集合中的组合！
然后for循环来处理这个字符集，代码如下：
class Solution {
List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return result;
}
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"};
//迭代处理
backTracking(digits, numString, 0);
return result;
}
StringBuilder temp = new StringBuilder();
public void backTracking(String digits, String[] numString, int index) {
if (index == digits.length()) {
result.add(temp.toString());
return;
}
//str 表示当前index对应的字符串
String str = numString[digits.charAt(index) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
backTracking(digits, numString, index + 1);
temp.deleteCharAt(temp.length() - 1);
}
}
}
本文含有隐藏内容，请 开通VIP 后查看