Recursion & Backtracking

发表于 | 更新于: | 分类于 | | 阅读次数:
字数统计: 1,616 | 阅读时长 ≈ 9

回溯：

在递归中暴力穷举，算法复杂度

难点

  • 状态回溯
  • 终止条件
  • 剪枝

一般的回溯问题

字符串问题

例题：No.17 Letter Combinations of a Phone Numbers

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 {
public:
    const string letterMap[10] = {
        " ",    // 0
        "",     //1
        "abc",  //2
        "def", //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs", //7
        "tuv",  //8
        "wxyz", //9
    };
/*    void findCombination(string digits, int index, string s, vector<string>& res) {
        if (index == digits.size()) {
            res.push_back(s); 
            return;
        }
        char c = digits[index];
        string letters = letterMap[c - '0'];
        for (int i = 0; i < letters.size(); i ++) {
            //状态回溯在调用中实现
            findCombination(digits, index + 1, s + letters[i], res);
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        findCombination(digits, 0, "", res);
        return res;
    }*/
    vector<string> findCombination(string digits, int index, string s) {
        vector<string> res;
        if (index == digits.size()) {
            res.push_back(s);
            return res;
        }
        char c = digits[index];
        string letters = letterMap[c - '0'];
        for (int i = 0; i < letters.size(); i ++) {
            vector<string> tmp = findCombination(digits, index + 1, s + letters[i]);
            for (auto v : tmp) res.push_back(v);
        }
        return res;
    }    
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res = findCombination(digits, 0, "");
        return res;
    }    
};

以前写得解

LeetCode练习题

  • No.93 Restore IP Addresses
  • No.131 Palindrome Parititioning

排列问题

例题：No.46 Permutation

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
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> p;
        int n = nums.size();
        vector<bool> used(n, false);
        generatePermutation(nums, p, used);
        return res;
    }
    void generatePermutation(vector<int>& nums, vector<int>& p, vector<bool>& used) {
        if (p.size() == nums.size()) {
            res.push_back(p);
            return;
        }
        for (int i = 0; i < nums.size(); i ++) {
            if (!used[i]) {
                used[i] = true;
                p.push_back(nums[i]);
                generatePermutation(nums, p, used);
                p.pop_back();       //状态回溯
                used[i] = false;    //状态回溯
            }
        }
    }    
};

以前的解
LeetCode练习题

  • No.47 Permutations II

组合问题

例题 No.77 Combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> res;
void generateCombinations(int n, int k, int start, vector<int>& tmp) {
    if (tmp.size() == k) {
        res.push_back(tmp);
        return;
    }
    for (int i = start; i <= n; i ++) {
        tmp.push_back(i);
        generateCombinations(n, k, start + 1, tmp);//错误之处，start应该为i
        tmp.pop_back(); //状态回溯
    }
}
vector<vector<int>> combine(int n, int k) {
    if (n <= 0) return {};
    vector<int> tmp;
    generateCombinations(n, k, 1, tmp);
    return res;
}

剪枝优化之后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> res;
void generateCombinations(int n, int k, int start, vector<int>& tmp) {
    if (tmp.size() == k) { // 终止条件改为 k == 0 否则无法退出
        res.push_back(tmp);
        return;
    }
    //for (int i = start; i <= n - (k - tmp.size()) + 1; i++) { //其他不改，只改这里也可以
    for (int i = start; i <= n - k + 1; i ++) {
        tmp.push_back(i);
        generateCombinations(n, k - 1, start + 1, tmp);//错误之处，start应该为i
        tmp.pop_back(); //状态回溯
    }
}
vector<vector<int>> combine(int n, int k) {
    if (n <= 0) return {};
    vector<int> tmp;
    generateCombinations(n, k, 1, tmp);
    return res;
}

LeetCode练习题

  • No.39 Combination Sum
  • No.40 Combination Sum II
  • No.216 Combination Sum III
  • No.78 Subsets
  • No.90 Subsets II
  • No.401 Binary Watch

二维平面上的回溯

二维平面上回溯的一般做法

例题： No.79 Word Search

floodfill算法(深度优先)

例题：No.200 Number of Islands

和普通回溯相比，没有状态回溯的过程

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
class Solution {
public:
    int m,n;
    int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    bool inArea(int x, int y) {
        return (x >= 0 && y >= 0 && x < m && y < n);
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> used(m, vector<bool>(n, false));
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && used[i][j] == false) {
                    count ++;
                    used[i][j] = true;
                    func(grid, used, i, j);
                }
            }
        }
        return count;
    }
    void func(vector<vector<char>>& grid, vector<vector<bool>>& used, int pos_x, int pos_y) {
                   
        for (int i = 0; i < 4; i ++) {
            int x = pos_x + d[i][0];
            int y = pos_y + d[i][1];
            if (inArea(x, y) && used[x][y] == false && grid[x][y] == '1') {
                used[x][y] = true;
                func(grid, used, x, y);
            }
        }
    
    }
};

LeetCode练习题

  • No.130 Surrounded Regions

    此题的神奇之处在于，如果用辅助数组来保存访问状态的话，会超时，也就是被注释掉的used数组；借助自身值来表示状态可以解决这个问题。

    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
    53
    54
    55
    56
    57
    58
    59
    60
    61
    class Solution {
    public:
        int m, n;
        int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        bool inArea(int x, int y) {
            return (x >= 0 && y >= 0 && x < m && y < n);
        }
        void func(vector<vector<char>>& board, int pos_x, int pos_y/*, vector<vector<bool>>& used*/) {
            //used[pos_x][pos_y] = true;
            board[pos_x][pos_y] = '*';
            for (int i = 0; i < 4; i++) {
                int x = pos_x + d[i][0];
                int y = pos_y + d[i][1];
                //if (inArea(x, y) && board[x][y] == 'O' && used[x][y] == false) {		
                if (inArea(x, y) && board[x][y] == 'O') {
                    func(board, x, y);
                }
            }
        }
        void solve(vector<vector<char>>& board) {
            if (board.empty()) return;
            m = board.size();
            n = board[0].size();
            
            vector<vector<bool>> used(m, vector<bool>(n, false));
            for (int i = 0; i < m; i ++) {
                int j = 0;
                if (board[i][j] == 'O') {
                    func(board, i, j);
                }
                j = n - 1;
                if (board[i][j] == 'O'){
                    func(board, i, j);
                }            
            }
            for (int j = 1; j < n - 1; j++) {
                int i  = 0;
                if (board[i][j] == 'O') {
                    func(board, i, j);
                }
                i = m - 1;
                if (board[i][j] == 'O') {
                    func(board, i, j);
                }            
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '*') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    };

  • No.417 Pacific Atlantic Water Flow

人工智能类应用

例题: No.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
37
38
39
40
41
42
vector<string> input;
vector<int> saved;
void func(int index, int n, vector<bool>& used, vector<vector<string>>& res) {
	for (int j = 0; j < index - 1; j++) {
		if (abs(j - (index - 1)) == abs(saved[j] - saved[index - 1])) return;
	}
	if (index == n) {
		vector<string> tmp;
		for (int i = 0; i < n; i ++)
			tmp.push_back(input[saved[i]]);
		res.push_back(tmp);
		return;
	}
	for (int i = 0; i < n; i ++) {
		if (used[i] == false) {
			used[i] = true;
			saved.push_back(i);
			func(index + 1, n, used, res);
			saved.pop_back();
			used[i] = false;
		}
	}
}
vector<vector<string>> solveNQueens(int n) {
	vector<bool> used(n, false);
	vector<vector<string>> res;
	for (int i = 0; i < n; i++) {
		string tmp = "";
		for (int j = 0; j < n; j++) {
			if (i == j) tmp += 'Q';
			else tmp += '.';
		}
		input.push_back(tmp);
	}
	func(0, n, used, res);
	return res;
}

比第一次写得简洁一些

LeetCode练习题

  • 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
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    vector<vector<char>> res;
    template<typename T>
    void print2DBoard(vector<vector<T>> board) {
    	int i = 0;
    	int j = 0;
    	for (auto v1 : board) {
    		for (auto v2 : v1) {			
    			cout << v2 << ' ';
    			if (++j % 3 == 0)
    				cout << "| ";
    		}
    		j = 0;
    		
    		cout  << endl;
    		if (++i % 3 == 0)
    			cout << "-----------------------" << endl;;
    	}
    	cout << endl;
    }
    template<typename T>
    void print2DVector(vector<vector<T>> board) {
    	for (auto v1 : board) {
    		for (auto v2 : v1) {
    			cout << v2 << '\t';
    		}
    		cout << endl << endl;
    	}
    	cout << endl;
    }
    void func(int i, int j, vector<vector<bool>>& row, vector<vector<bool>>& col, vector<vector<bool>>& grid, vector<vector<char>>& board) {
    	if (i == 9) {
    		res = board;
    		return;
    	}
    	if (board[i][j] == '.') {
    		for (int k = 0; k < 9; k++) {
    			if (row[i][k] == false && col[j][k] == false && grid[(i / 3) * 3 + j / 3][k] == false) {
    				board[i][j] = k + '1';
    				row[i][k] = true;
    				col[j][k] = true;
    				grid[(i / 3) * 3 + j / 3][k] = true;
    				func((i + (j + 1) / 9), (j + 1) % 9, row, col, grid, board);
    				grid[(i / 3) * 3 + j / 3][k] = false;
    				col[j][k] = false;
    				row[i][k] = false;
    				board[i][j] = '.';
    			}
    		}
    	}
    	else {
    		func((i + (j + 1) / 9), (j + 1) % 9, row, col, grid, board);
    	}
    }
    void solveSudoku(vector<vector<char>>& board) {
    	vector<vector<bool>> row(9, vector<bool>(9, false));
    	vector<vector<bool>> col(9, vector<bool>(9, false));
    	vector<vector<bool>> grid(9, vector<bool>(9, false));
    	for (int i = 0; i < 9; i++) {
    		for (int j = 0; j < 9; j++) {
    			if (board[i][j] != '.') {
    				int num = board[i][j] - '0';
    				row[i][num - 1] = true;
    				col[j][num - 1] = true;
    				grid[(i / 3) * 3 + j / 3][num - 1] = true;
    			}
    		}
    	}
    	//cout << "print row" << endl << "-----------------------" << endl;
    	//print2DVector(row);
    	//cout << "print col" << endl << "-----------------------" << endl;
    	//print2DVector(col);
    	//cout << "print grid" << endl << "-----------------------" << endl;
    	//print2DVector(grid);
    	func(0, 0, row, col, grid, board);
    	board = res;
    	//print2DBoard(board);
    }
    int main() {
    	vector<vector<char>> input;
    	string str[9] = { "..9748...", "7........", ".2.1.9...", "..7...24.", ".64.1.59.", ".98...3..", "...8.3.2.", "........6", "...2759.." };
    	for (auto s : str) {
    		input.push_back(vector<char>(s.begin(), s.end()));
    	}
    	print2DBoard(input);
    	solveSudoku(input);
    	print2DBoard(res);
    	return 0;
    }

imag