代码随想录算法训练营19-回溯1

77. 组合

画出来的树是这样

记录所有组合，一个变量current装当前的处理结果，一个res装所有的处理的结果

回溯三部曲：

• 参数：给定两个整数 n 和 k，以及每层for循环的起点
• 终止条件：current里面的数量 == k，就把current收割，并return
• 每层处理的逻辑
  • for循环的起点：startIndex；for循环的终点：arr.length
  • 每次处理的逻辑：
    • current.add(arr[i])
    • backtracing(n,k,i+1)
    • current.removelast

下面的代码还可以剪枝优化

class Solution {List<List<Integer>> res;List<Integer> curent;public List<List<Integer>> combine(int n, int k) {res = new LinkedList<>();curent = new LinkedList<>();backtracing(n, k, 1);return res;}void backtracing(int n, int k, int startIndex) {if (curent.size() == k) {LinkedList<Integer> temp = new LinkedList<>(curent);res.add(temp);}for (int i = startIndex; i < n+1; i++) {curent.add(i);backtracing(n, k, i + 1);curent.remove(curent.size() - 1);}}
}

216.组合总和III

画出抽象的树

这一题和上一题的最大区别在于终止条件有点不一样

记录所有组合，一个变量current装当前的处理结果，一个res装所有的处理的结果

回溯三部曲

• 参数：k，startIndex
• 终止条件
  • 如果current.size == k
    • 如果current加起来不是n，直接return
    • 如果current加起来是n，收集到res中
• 每层处理
  • for循环的起点终点：i = startIndex; i < 10; i++
  • 每层for循环要干的事情
    • current.add(i)
    • backtracing(k, i + 1)
    • current.removeLast

还是一样，可以剪枝优化

class Solution {List<List<Integer>> res;List<Integer> current;int target;public List<List<Integer>> combinationSum3(int k, int n) {res = new LinkedList<>();current = new LinkedList<>();target = n;backtracing(k, 1);return res;}void backtracing(int k, int startIndex) {if (current.size() == k) {if (getListSum(current) == target) {List<Integer> temp = new LinkedList<>(current);res.add(temp);return;} else {return;}}for (int i = startIndex; i < 10; i++) {current.add(i);backtracing(k, i + 1);current.remove(current.size() - 1);}}int getListSum(List<Integer> list) {int sum = 0;for (int i = 0; i < list.size(); i++) {sum += list.get(i);}return sum;}
}

17.电话号码的字母组合

这道题我感觉区别就在于每次for循环遍历的东西是动态变化的，因此需要再入参的地方传入

准备工作：准备一个二维列表，大小为8，存储2-9所代表的字母。

List<List<Integer>> store = Arrays.asList(Arrays.asList("a", "b", "c"),Arrays.asList("d", "e", "f"),Arrays.asList("g", "h", "i"),Arrays.asList("j", "k", "l"),Arrays.asList("m", "n", "o"),Arrays.asList("p", "q", "r","s"),Arrays.asList("t", "u", "v"),Arrays.asList("w", "x", "y","z"),
);

记录所有组合，一个变量current装当前的处理结果，一个res装所有的处理的结果

回溯三部曲

• 入参：当前处理到的数字的下标i
• 终止条件
  • current.size == 输入字符串的长度，则收割保存
• 每层的处理逻辑
  • for循环的起点终点：i = 0; i < store.get(number - 2).size; i++
  • for循环每次要干的事情
    • current.add
    • backtracing(当前处理的数字的下一个数字，也就是i+1)
    • current.removeLast

class Solution {List<List<String>> store;char[] digitsArr;StringBuilder current;List<String> res;public List<String> letterCombinations(String digits) {store = Arrays.asList(Arrays.asList("a", "b", "c"),Arrays.asList("d", "e", "f"),Arrays.asList("g", "h", "i"),Arrays.asList("j", "k", "l"),Arrays.asList("m", "n", "o"),Arrays.asList("p", "q", "r", "s"),Arrays.asList("t", "u", "v"),Arrays.asList("w", "x", "y", "z"));digitsArr = digits.toCharArray();current = new StringBuilder();res = new LinkedList<>();if (digits.equals("")) return res;bk(0);return res;}void bk(int index) {if (current.length() == digitsArr.length) {String temp = current.toString();res.add(temp);return;}int number = Integer.parseInt(String.valueOf(digitsArr[index]));List<String> listForSearch = store.get(number - 2);for (int i = 0; i < listForSearch .size(); i++) {current.append(listForSearch .get(i));bk(index + 1);current.deleteCharAt(current.length() - 1);}}
}