for循环横向遍历，递归纵向遍历，回溯不断调整结果集
画树，回溯要画树
77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
result.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTracking(n,k,1);
return result;
}
void backTracking(int n, int k, int startIndex){
if(path.size()==k){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n; i++) {
path.add(i);
backTracking(n,k,i+1);
path.removeLast();//回溯
}
}
}
剪枝操作优化代码：
for (int i = startIndex; i <= n; i++) {
剪枝：
for (int i = startIndex; i <=n-(k-path.size())+1; i++) {
path.size() 是当前路径里元素的个数
k-path.size() 是还需要的元素个数
n-(k-path.size())+1 至多走到哪里
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
- 这题和上面一题十分相似，就浅浅改了一下上面的代码
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
if(k > n){//如果n小于k的话直接返回
return result;
}
backTracking(k,n,1);
return result;
}
void backTracking(int k, int n, int startIndex){
if(path.size()==k){//数组的长度达到标准之后
int sum = 0;
for (Integer p : path) {
sum +=p;
}
if(sum == n){//看数组中数字之和是否达到标准
result.add(new ArrayList<>(path));
}
return;
}
for (int i = startIndex; i <= n; i++) {
path.add(i);
backTracking(k,n,i+1);
path.removeLast();
}
}
}
- 结果超出时间限制，因为没有剪枝
for (int i = startIndex; i <= Math.min(n-(k*(k-1)/2),9) ; i++) {
- k*(k-1)/2 是对前k-1个数的求和
- n-(k*(k-1)/2) 和 9 取最小是怕n太大，k太小导致path里的数 > 9
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
- 把按键上对应的数字转换成字符串letters，遍历的时候要遍历的是字符串
class Solution {
List<String> result = new ArrayList<>();
static String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//下标就是按键上的数字
public List<String> letterCombinations(String digits) {
if(digits.equals(""))
return result;//对特殊情况特殊处理
backTracking(digits,0);//从零开始
return result;
}
static StringBuilder sb = new StringBuilder();
void backTracking(String digits, int index){
//index指的是当前对哪个数字进行处理
if(sb.length()==digits.length()){
result.add(sb.toString());
return;
}
String letter = letters[(digits.charAt(index))-'0'];//取当前下标对应的字符串
for (int i = 0; i < letter.length(); i++) {
sb.append(letter.charAt(i));
backTracking(digits,index+1);
sb.deleteCharAt(sb.length()-1);
}
}
}