回溯法经典难题解析

本文将通过几个经典的回溯问题，展示回溯算法的应用及其在解决问题时的核心思想和技巧。这些问题包括全排列、全排列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. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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);}
};