代码随想录算法训练营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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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"),
);
1
2
3
4
5
6
7
8
9
10

记录所有组合，一个变量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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43