学习目标：
每天复习代码随想录上的题目1-2道算法（时间充足可以继续）
今日碎碎念：
1）滴滴开了暑期实习。
2）今天开始是回溯篇，然后是贪心以及dp，保持打卡！加油啦！
3）今天要做的事情就是，完成算法打卡，然后总结实习的工作，整理好自己的思路，应对后面可能的面试。
力扣刷题
算法
力扣77：77. 组合
未剪枝优化
class Solution {
List<List<Integer>> res;
List<Integer> list;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
list = new ArrayList<>();
back(n,k,1);
return res;
}
public void back(int n,int k,int startIndex){
//对于回溯最重要的就是确定终止条件
if(list.size() == k){
//如果小结果集里面的个数为k，就表示要回溯了
res.add(new ArrayList<Integer>(list));
return;
}
//如果没满k，就得继续加元素到小结果集里面
for(int i = startIndex;i<=n;i++){
list.add(i);
//进入下一轮选择
back(n,k,i+1);
//要把添加进去的末尾元素去除
list.remove(list.size()-1);
}
}
}剪枝优化
解答思路：
1）当我们继续去找元素的时候有个隐性条件，就是我们最终的小结果集的数量一定得满足k，如果我剩下的数量无法满足k，那就没必要往后找了
2）比如，n=4，k=4的情况下，不难想出我们的小结果集只有1234这一种情况，而不可能会出现234这种情况。那么当我挑出来了1234这种情况的时候，判断后续数量很明显长度最大为3，不满足k，因此没必要继续遍历
class Solution {
List<List<Integer>> res;
List<Integer> list;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
list = new ArrayList<>();
back(n,k,1);
return res;
}
public void back(int n,int k,int startIndex){
//对于回溯最重要的就是确定终止条件
if(list.size() == k){
//如果小结果集里面的个数为k，就表示要回溯了
res.add(new ArrayList<Integer>(list));
return;
}
//如果没满k，就得继续加元素到小结果集里面
//剪枝说明：如果剩下的数量不足以组成我要求的list了，就没必要往后走了
for(int i = startIndex;i<=n-(k-list.size())+1;i++){
list.add(i);
//进入下一轮选择
back(n,k,i+1);
//要把添加进去的末尾元素去除
list.remove(list.size()-1);
}
}
}力扣216：216. 组合总和 III
解答思路：
1）与上道题思路是类似的，多了剪枝判断而已
class Solution {
List<List<Integer>> res;
List<Integer> list;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<>();
list = new ArrayList<>();
back(k,n,1,0);
return res;
}
public void back(int k,int n,int index,int sum){
//剪枝：如果当前和已经大于n，说明不需要往后走了，因为题目给定的集合是有序的
if(sum > n) return;
//终止条件：小结果集为k就退出，如果sum为n就加入结果集
if(list.size() == k){
if(sum == n) res.add(new ArrayList<>(list));
return;
}
//开始回溯以及剪枝。剪枝同77题，后面的元素不足以满足数量就不需要继续遍历了
for(int i = index;i<=9-(k-list.size())+1;i++){
list.add(i);
//计算当前总和
sum+=i;
back(k,n,i+1,sum);
//回溯
list.remove(list.size()-1);
sum-=i;
}
}
}力扣17：17. 电话号码的字母组合
解答思路：看注释即可
class Solution {
//设置全局列表存储最后的结果
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
back(digits,numString,0);
return list;
}
//大量拼接用StringBuilder
StringBuilder sb = new StringBuilder();
public void back(String digits,String[] numString,int index){
//终止条件：index是记录从digits里面选取第几个元素
if(index == digits.length()){
list.add(sb.toString());
return;
}
//取出当前按下的数字代表的字符串
String str = numString[digits.charAt(index)-'0'];
for(int i = 0;i<str.length();i++){
sb.append(str.charAt(i));
back(digits,numString,index+1);
sb.deleteCharAt(sb.length()-1);
}
}
}力扣39：39. 组合总和
解答思路：看注释即可
class Solution {
List<List<Integer>> res;//大结果集
List<Integer> list;//小结果集
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList<>();
list = new ArrayList<>();
//因为原数组是没有排序的，先对原数组进行排序
Arrays.sort(candidates);
back(candidates,target,0,0);
return res;
}
//参数：数组，目标和，当前和，当前位置（下标）
public void back(int[] candidates,int target,int sum,int index){
//终止条件: sum == target
if(sum == target){
//将小结果集加入大结果集
res.add(new ArrayList<>(list));
return;
}
//因为每个数字可以无限制重复被选取，所以index得传入i
for(int i = index;i<candidates.length;i++){
if(sum+candidates[i] > target) break;
list.add(candidates[i]);
back(candidates,target,sum+candidates[i],i);
list.remove(list.size()-1);
}
}
}
