Back Tracking（回溯）相关算法与经典问题整理

Posted on | Edited on | In |

我理解的回溯法，简单来说，就是遍历，就是DFS！

其它的都是想想都知道的：谁不知道碰到走不下去的就回去，谁不知道碰到走不下去退回到上一步，而不是退到初始的地方。

基本解决思想

记录之前的操作，这样可以退回到上一步的操作，进而进行下一个candidate的试探。

考虑要点

1. 非法结束

当进入非法的状态的时候，执行怎样的操作，通常在递归的过程中，直接return结束即可，如果有特殊的操作，需要进行特殊的处理。

2. 满足条件

满足条件的情况下，需要进行怎样的操作，比如将正确的值记录下来，返回成功的状态等。

3. 遍历试探

这一步是最重要的一步，也是最繁琐的一步。

需要遍历所有可能的选择，往前“走一步”，在“走了一步”的状态下进行新的一轮操作。操作完成之后，需要“回退一步“到原来的状态。

这个遍历可能出现的情况有：二维地图的上下左右遍历，找数组满足条件的值得遍历数组等。

相关问题

以下问题都能够或多或少体现上述的三个要点。

subset problem

LeetCode 78. Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<int>& nums, int start_idx) {
        res.push_back(curr);
        for (int i = start_idx; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            backtrack(res, curr, nums, i + 1);
            curr.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> curr;
        backtrack(res, curr, nums, 0);
        return res;
    }
};

LeetCode 90. Subsets II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    void backtrack(vector<vector<int>>& res, vector<int>& curr, vector<int>& nums, int start_idx) {
        res.push_back(curr);
        for (int i = start_idx; i < nums.size(); i++) {
            if (i > start_idx && nums[i] == nums[i - 1]) // 注意如何跳过重复！！！
                continue;
            curr.push_back(nums[i]);
            backtrack(res, curr, nums, i + 1);
            curr.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> curr;
        sort(nums.begin(), nums.end());
        backtrack(res, curr, nums, 0);
        return res;
    }
};

N-Queen

LeetCode 51. N-Queens

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
class Solution {
private:
    bool check(vector<string>& curr, int r, int c, int n) {
        for (int i = 1; i <= r; i++) {
            if (c - i >= 0 && curr[r - i][c - i] == 'Q' ||
               curr[r - i][c] == 'Q' ||
               c + i < n && curr[r - i][c + i] == 'Q')
                return false;
        }
        return true;
    }
    void fill(vector<vector<string>>& res, vector<string>& curr, int row, int n) {
        if (row >= n) {
            res.push_back(curr);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check(curr, row, i, n)) {
                curr[row][i] = 'Q';
                fill(res, curr, row + 1, n);
                curr[row][i] = '.';
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> curr;
        for (int i = 0; i < n; i++) {
            string s(n, '.');
            curr.push_back(s);
        }
        fill(res, curr, 0, n);
        return res;
    }
};

Sudoku

LeetCode 37. Sudoku Solver

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
44
45
46
47
48
49
50
51
52
class Solution {
private:
    bool check(vector<vector<char>>& board, int r, int c) {
        for (int i = 0; i < 9; i++) {
            if (i != r && board[i][c] == board[r][c])
                return false;
        }
        for (int j = 0; j < 9; j++) {
            if (j != c && board[r][j] == board[r][c])
                return false;
        }
        int r_div = r / 3;
        int c_div = c / 3;
        for (int i = r_div * 3; i < (r_div + 1) * 3; i++) {
            for (int j = c_div * 3; j < (c_div + 1) * 3; j++) {
                if ((i != r || j != c) && board[i][j] == board[r][c])
                    return false;
            }
        }
        return true;
    }
    bool fill(vector<vector<char>>& board, int r, int c) {
        int i, j;
        bool found_next = false;
        for (i = r; i < 9; i++) {
            for (j = c; j < 9; j++) {
                if (board[i][j] == '.') {                    
                    found_next = true;
                    break;
                }
            }
            if (found_next)
                break;
            j = 0;
        }
        if (i >= 9)
            return true;
        for (char k = '1'; k <= '9'; k++) {
            board[i][j] = k;
            if (check(board, i, j)) {
                if (fill(board, r, c))
                    return true;
            }
            board[i][j] = '.';
        }
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        fill(board, 0, 0);
    }
};

参考

https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)