回溯：当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。
如果在回溯法中使用了辅助的全局变量，则一定要及时把它们恢复原状。特别地，若函数有多个出口，则需在每个出口处回复被修改的值。
Leetcode 51. N-Queens
给定$n$，输出$n$皇后问题的所有解。
class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<int>> vis(3, vector<int>(2 * n, 0)); vector<int> C(n, 0); vector<vector<string>> res; search(vis, 0, n, res, C); return res; } void search(vector<vector<int>>& vis, int cur, int n, vector<vector<string>>& res, vector<int>& C){ if(cur == n){ vector<string> tmp(n, string(n, '.')); for(int i = 0; i < n; ++i){ tmp[i][C[i]] = 'Q'; } res.push_back(tmp); } else{ for(int i = 0; i < n; ++i){ if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){ C[cur] = i; vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1; search(vis, cur + 1, n, res, C); vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0; } } } } };
Leetcode 52. N-Queens II
给定$n$，输出$n$皇后解的个数。
class Solution { public: int totalNQueens(int n) { vector<vector<int>> vis(3, vector<int>(2 * n, 0)); int total = 0; search(vis, total, 0, n); return total; } void search(vector<vector<int>>& vis, int& total, int cur, int n){ if(cur == n) total++; else{ for(int i = 0; i < n; ++i){ if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){ vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1; search(vis, total, cur + 1, n); vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0; } } } } };