216. 组合总和 III
题目链接：组合总和 III
题目描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
解题思路：
本题和组合问题十分相似，按照剪支三部曲可以很好地解决。
代码实现：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
int start = 1;
public List<List<Integer>> combinationSum3(int k, int n) {
if (n < 0) {
//当剩下元素和小于-剪支
return res;
}
if (k == 0) {
if (n == 0) {
//当满足剩余元素和剩余和同时为零找到最终结果
res.add(new ArrayList<>(path));
return res;
}
}
for (int i = start; i < 10; i++) {
path.add(i);
start=i+1;//防止重复从下一个元素开始
combinationSum3(k - 1, n - i);
path.removeLast();
}
return res;
}
}
17. 电话号码的字母组合
题目链接：电话号码的字母组合
题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解题思路：
本题也不是很难，只要搞清楚回溯法是横向遍历一层，纵向递归，
从本题题目上可以看出，横向遍历每到一个数字的代表字母，纵向递归输入字符串的每个字母，因此，回溯的终止条件就是递归到最后一个字母。如此就可根据回溯三部曲，比较简单地写出代码。
代码实现：
class Solution {
List<String> res = new ArrayList<>();//记录最终结果
StringBuilder path = new StringBuilder();//记录过程中路径
public List<String> letterCombinations(String digits) {
if(digits == null||digits.length()==0){
return res;
}
String[] numString = {
"","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//对应2-9的代表字母
backtraversal(digits,numString,0);
return res;
}
public void backtraversal(String digits,String[] numString,int len){
//len表示当前path中元素个数、
//当len中元素等于输入字符串长度说明递归到最后
if(len == digits.length()){
res.add(path.toString());
return ;
}
int n = digits.charAt(len)-'0';
//横向遍历数字代表的字母
for(int i =0 ; i<numString[n].length();i++){
path.append(numString[n].charAt(i));
backtraversal(digits,numString,len+1);
path.deleteCharAt(len);
}
}
}
