本文将通过几个经典的回溯问题，展示回溯算法的应用及其在解决问题时的核心思想和技巧。这些问题包括全排列、全排列II、N皇后以及数独问题，本文将分别介绍每个问题的思路与实现。
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
思路：
对于给定的数组，我们通过回溯法逐一选择数组中的元素，并将其加入当前的排列中。
需要一个 visited 数组来记录每个元素是否已经被使用过，避免重复排列。
每当排列的长度等于原数组长度时，表示当前排列已完成，加入结果集。
核心技巧：
在递归过程中使用 visited 数组来确保每个元素只被使用一次。
递归的终止条件是当当前排列的长度等于数组长度时，说明已经形成一个完整的排列。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
unordered_set<int> node;
void backfind(vector<int>& nums){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0; i<nums.size(); i++){
if(node.find(nums[i])!=node.end()){continue;}
node.insert(nums[i]);
path.push_back(nums[i]);
backfind(nums);
node.erase(nums[i]);
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
backfind(nums);
return res;
}
};
47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路：先对数组进行排序，使得相同的元素相邻。使用 visited 数组来标记每个元素是否已经被访问过，同时利用排序后的数组来跳过已经处理过的重复元素。在每次递归时，检查当前元素与前一个元素是否相同，如果相同且前一个元素未被访问，则跳过当前元素。
核心技巧：排序保证了相同元素相邻，从而避免了重复排列。通过回溯的剪枝技巧，避免在同一层的递归中重复访问相同的元素。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backfind(vector<int>& nums, vector<bool>& visited){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i=0; i<nums.size(); i++){
if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false){continue;}
//同层树重复的跳过，同层的上一个visited是没访问过的(回溯)
//visited[i-1]==true也是可以滴
if(visited[i]){continue;}
visited[i]=true;
path.push_back(nums[i]);
backfind(nums,visited);
visited[i]=false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> visited(nums.size(), false);
backfind(nums,visited);
return res;
}
};
51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
思路：使用回溯法逐行放置皇后，每放置一个皇后就递归处理下一行。
在每次尝试放置皇后时，检查该位置是否会与已放置的皇后发生冲突，即检查同列、左斜线和右斜线是否已有皇后。
核心技巧：使用三种标记（列标记、左斜线标记、右斜线标记）来有效判断是否可以放置皇后。
通过递归实现行的逐步尝试，并在放置皇后后继续处理下一行。
class Solution {
public:
vector<vector<string>> res;
void find(int n, int row, vector<string>& rowChess){
if(row==n){
res.push_back(rowChess);
return;
}
for(int col=0; col<n; col++){
if(isQ(rowChess,row,col,n)){
rowChess[row][col]='Q';
find(n, row+1, rowChess);
rowChess[row][col]='.';
}
}
}
bool isQ(vector<string>& rowChess, int row, int col, int n){
//先遍历列
for(int i=0; i<row; i++){
if(rowChess[i][col]=='Q'){
return false;
}
}
//再检查45°线
for(int i=row-1, j=col-1; i>=0&&j>=0; i--,j--){
if(rowChess[i][j]=='Q'){
return false;
}
}
//再检查135°线
for(int i=row-1, j=col+1; i>=0&&j<n; i--,j++){
if(rowChess[i][j]=='Q'){
return false;
}
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> rowChess(n, string(n,'.'));
find(n, 0, rowChess);
return res;
}
};
37. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
思路：使用回溯法逐步填充数独中的空格。每次选择一个空格，尝试填入数字 1-9，并检查填入的数字是否合法。如果合法，递归处理下一个空格；如果不合法，回溯并尝试其他数字。
核心技巧：使用一个 isOK 函数来检查当前填入的数字是否符合数独的规则。
回溯的终止条件是所有空格都被填充且合法时，返回解。
class Solution {
public:
bool backsolve(vector<vector<char>>& board){
for(int i=0; i<board.size(); i++){
for(int j=0; j<board[0].size(); j++){
if(board[i][j]=='.'){
for(char c='1'; c<='9'; c++){
if(isOK(board,i,j,c)){
board[i][j]=c;
if(backsolve(board)) return true;
board[i][j]='.';
}
}return false;
}
}
}return true;
}
bool isOK(vector<vector<char>>& board, int row, int col, char val){
//行里面寻找有没有重复的
for(int i=0; i<9; i++){
if(board[i][col]==val){
return false;
}
}
//列里面寻找有没有重复的
for(int j=0; j<9; j++){
if(board[row][j]==val){
return false;
}
}
int startrow=(row/3)*3;
int startcol=(col/3)*3;
for(int i=startrow; i<startrow+3; i++){
for(int j=startcol; j<startcol+3; j++){
if(board[i][j]==val){
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backsolve(board);
}
};
