Backtracking Algorithm Notes

Basics

  • 路径，已做出的选择，previous choices (track)
  • 可选列表，next step
  • 结束条件，end point
1
2
3
4
5
6
7
8
9
10
11
12
result = [] // usually the result needs to be a list
function backtrack(current_route, available_list)
    if reach_to_the_end_point
        result.add(current_route)
        return

    for choice in available_list
        make a choice
        backtrack(updated_route, updated_available_list)
        restore the choice
        restore the route
        add the previous choice to the available list

Problems 🥳

46 Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        // provide a empty route at the beginning
        List<Integer> route = new ArrayList<>();
        backtrack(route, nums);
        return res;
    }
    private void backtrack(List<Integer> route, int[] nums) {
        if(route.size() == nums.length) {
            res.add(new ArrayList(route));
            return;
        }
        for (int num: nums) {
            if (route.contains(num)) {
                continue;
            }
            route.add(num);
            backtrack(route, nums);
            route.remove(route.size() - 1);
        }
    }
}

In this example, use int[] nums instead of tracking available list in each iteration.

A minor issue is, in res.add(new ArrayList(route)), new ArrayList(route) is required, otherwise, the remove method will modify the list in the res, then, the result will all be empty lists.

51 N-Queens 👸🏻

To determine the 3 basic elements

  1. route. I will set the route as a list of integers at the beginning, since it will be more convenient to debug later ( e.g [1, 3, 0, 2] as the first solution provided in the problem description)
  2. avaliable list. [0, 1, 2, 3, …, n - 1] obviously.
  3. end point. The size of the list.
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
class Solution {
    private List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        List<Integer> route = new ArrayList<>();
        backtrack(route, n);
        return res;
    }
    private void backtrack(List<Integer> route, int n) {
        if (route.size() == n) {
            List<String> routeInString = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder str = new StringBuilder();
                // print dot
                for(int j = 0; j < route.get(i); j++) {
                    str.append(".");
                }
                // print Q
                str.append("Q");
                // print remaining dot
                for (int z = 0; z < n - route.get(i) - 1; z++) {
                    str.append(".");
                }
                routeInString.add(str.toString());
            }
            res.add(routeInString);
        }

        for (int i = 0; i < n; i++) {
            if (route.contains(i)) continue;
            if(!addable(route, i)) continue;
            route.add(i);
            backtrack(route, n);
            route.remove(route.size() - 1);
        }
    }
    private boolean addable(List<Integer> route, int i) {
        int rows = route.size();
        for (int m = 0; m < rows; m++) {
            if (Math.abs(rows - m) == Math.abs(i - route.get(m))) return false;
        }
        return true;
    }
}

An issue is when checking whether i can be added to the route, Math.abs() is required or the number of results will be larger than what is expected.