很高興又堅持了7天。

算法（回溯）

77. 組合

class Solution {List<Integer> list = new LinkedList<>();List<List<Integer>> llist = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {back(n,k,1);return llist;}public void back(int n,int k,int index){if(list.size() == k){llist.add(new LinkedList<>(list));return;}//剪枝優化：舉個例子，當n=k的時候，很明顯路只有一條，因此后面的都無需再遍歷//剪枝從什么角度入手去考慮呢？for(int i = index;i<=(n - (k-list.size()) + 1);i++){list.add(i);back(n,k,i+1);list.remove(list.size()-1);}}
}

---

216. 組合總和 III

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){//剪枝if(sum > n){return;}//終止條件if(list.size() == k){if(sum == n){res.add(new ArrayList<>(list));}return;}//剪枝：如果當前和已經大于目標值，很顯然沒必要繼續遍歷for(int i = index;i<=9;i++){if(sum+i > n){continue;}sum+=i;list.add(i);back(k,n,i+1,sum);sum-=i;list.remove(list.size()-1);}}
}

---

17. 電話號碼的字母組合

class Solution {//設置全局列表存儲最后的結果List<String> list = new ArrayList<>();String[] num = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits.equals("") || digits == null) return list;back(digits,0);return list;}StringBuilder tmp = new StringBuilder();public void back(String digits,int index){//終止條件if(index == digits.length()){list.add(tmp.toString());return;}//通過index找到當前按下的鍵String now = num[digits.charAt(index)-'0'];//遍歷可能的組合for(int i = 0;i<now.length();i++){tmp.append(now.charAt(i));back(digits,index+1);tmp.deleteCharAt(tmp.length()-1);}}
}

---

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 tar,int idx,int sum){if(sum == tar){res.add(new ArrayList<>(list));return;}for(int i = idx;i<candidates.length;i++){if(sum + candidates[i] > tar){continue;}sum+=candidates[i];list.add(candidates[i]);back(candidates,tar,i,sum);list.remove(list.size()-1);sum-=candidates[i];}}}

---

40. 組合總和 II

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();//利用一個數組來記錄某數字是否被使用過boolean[] used;public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length];Arrays.sort(candidates);Arrays.fill(used,false);back(candidates,target,0,0);return res;}public void back(int[] candidates, int target,int sum,int idx){if(sum == target){res.add(new LinkedList<>(list));return;}for(int i = idx;i<candidates.length;i++){//剪枝if(sum + candidates[i] > target) continue;//當前位和前一位相同的情況下，如果前一位已經為false，說明已經被選擇過了，跳過if(i>0 && candidates[i]==candidates[i-1] && used[i-1] == false){continue;}sum+=candidates[i];list.add(candidates[i]);used[i] = true;back(candidates,target,sum,i+1);used[i] = false;list.remove(list.size()-1);sum-=candidates[i];}}
}

---

131. 分割回文串

class Solution {List<List<String>> res = new ArrayList<>();List<String> list;public List<List<String>> partition(String s) {list = new ArrayList<>();back(s,0);return res;}public void back(String s,int idx){//如果idx到/超過了s的長度說明已經可以加入集合了if(idx >= s.length()){res.add(new ArrayList<>(list));return;}for(int i = idx;i<s.length();i++){if(isValid(idx,i,s)){//當前區間是回文串String tmp = s.substring(idx,i+1);list.add(tmp);back(s,i+1);list.remove(list.size()-1);}else{continue;}}}//判斷是否為回文串public boolean isValid(int start,int end,String s){while(start<end){if(s.charAt(start) != s.charAt(end)) return false;start++;end--;}return true;}
}

---

思考

剪枝從什么角度去入手呢？

剩余的數量是否足夠我去湊成結果集

剩余的數量還有沒有必要讓我繼續去跑下一輪來選擇？

---

補充知識點

今天無知識點的補充，明天出發去北京啦