216.组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
解析：
读懂题很重要，题目说的很清楚，第一要是组合，组合根据回溯理论基础那一章节表示，组合意味着没有顺序，比如[1,2,4]和[1,4,2]是一种。第二表示不重复，每个数字只能用一次。
class Solution {
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(k,n,0,1);
return res;
}
void backTracking(int k, int n, int sum,int startIndex){
if(sum > n) return;
if(path.size() > k) return ;
if(path.size() == k && sum == n){
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9; i++){
path.add(i);
sum += i;
backTracking(k,n,sum,i+1);
sum -= i;
path.remove(path.size()-1);
}
}
}剪枝
class Solution {
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(k,n,0,1);
return res;
}
void backTracking(int k, int n, int sum,int startIndex){
if(sum > n) return;
if(path.size() > k) return ;
if(path.size() == k && sum == n){
res.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9+1-k+path.size(); i++){
path.add(i);
sum += i;
backTracking(k,n,sum,i+1);
sum -= i;
path.remove(path.size()-1);
}
}
}7.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
- 输入："23"
- 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解析：
可以按任意顺序输出，即代表组合问题。其次，要对数字到字母的映射进行编写，可以写成一个字符串数组，按0-9的下标写出对应的字母映射。
输入的digits长度，就是递归的深度。每个数字映射的字符串长度，是for循环的次数。
class Solution {
List<String> list = new ArrayList<>(); //保存最后的结果
public List<String> letterCombinations(String digits) {
if(digits.length() == 0 || digits == null) return list;
String[] numStr = {"","", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backTracking3(digits,numStr,0);
return list;
}
StringBuilder s = new StringBuilder(); //StringBuilder类
//回溯算法的参数，digits为输入的字符串，numStr为数字与字符串的映射，index为输入的数字字符串的指向位置
void backTracking3(String digits, String[] numStr, int index){
//回溯终止条件
if(index == digits.length()){
list.add(s.toString());
return;
}
//确定单层遍历逻辑
String str = numStr[digits.charAt(index)-'0'];
for (int i = 0; i < str.length(); i++) {
s.append(str.charAt(i));
backTracking3(digits,numStr,index+1); //这里，只要给出一层的处理后，下一层直接下一个数字
s.deleteCharAt(s.length()-1);
}
}
}