1.組合

（1）模板

void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
}

重要參數，List<List<Integer>> res ，Deque<Integer> path，?int startIndex

class Solution {List<List<Integer>> res = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public List<List<Integer>> combine(int n, int k) {backtrack(n, 1, k);return res;}// startIndex 就是防止出現重復的組合private void backtrack(int n, int startIndex, int k) {if (path.size() == k) {// path路徑中存放的數達到k個即放入結果res.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n; i++) { // 范圍 [1, n] path.add(i);backtrack(n, i + 1, k);path.removeLast();}}
}

（2）優化剪枝，主要是對選過的數字進行剪除

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置

2.組合總和III

回溯算法處理，sum來統計path里元素的總和，處理過程 和 回溯過程是一一對應的，處理有加，回溯就要有減！ for循環內一個是sum的變化，一個是path的變化

class Solution {List<List<Integer>> res = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public List<List<Integer>> combinationSum3(int k, int n) {backtrack(k, n, 1, 0);return res;}private void backtrack(int k, int targetsum, int startIndex, int sum) {if (path.size() == k) {if (sum == targetsum) res.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= 9; i++) {sum += i;path.add(i);backtrack(k, targetsum, i + 1, sum);sum -= i;path.removeLast();}}
}

3.電話號碼的數字組合

對字符串的回溯可以用StringBuilder來處理

停止條件 {

?res.add(path.toString());

}

for循環內 {

????????????????path.append(str.charAt(i));
? ? ? ? ? ? ? ? dfs(digits, dept + 1);// 遞歸
? ? ? ? ? ? ? ? path.deleteCharAt(dept);// 回溯

}

class Solution {List<String> res = new ArrayList<>();//定義一個返回的結果集StringBuilder path = new StringBuilder();//定義一個存儲路徑的可變字符的變量Map<Character,String> map = new HashMap<>(){{//定義哈希表表示字符串的所有可能put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};public List<String> letterCombinations(String digits) {       if(digits.length() == 0) {return res;}dfs(digits, 0);return res;}public void dfs(String digits, int dept) {// 停止條件：當遞歸到底層的時候，將路徑上的參數加入結果集中 if (dept == digits.length()) {res.add(path.toString());return;} else {//定義一個存儲字符串的數字char digit = digits.charAt(dept);//定義一個存儲數字對應的所有可能字符串String str = map.get(digit);int len = str.length();// 遍歷字符串for (int i = 0; i < len; i++) {path.append(str.charAt(i));dfs(digits, dept + 1);// 遞歸path.deleteCharAt(dept);// 回溯}}}
}