回溯排列+棋盘问题篇--代码随想录算法训练营第二十三天| 46.全排列，47.全排列 II，51. N皇后，37. 解数独

46.全排列

题目链接：. - 力扣（LeetCode）

讲解视频：

组合与排列的区别，回溯算法求解的时候，有何不同？

题目描述：

给定一个不含重复数字的数组 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]]

解题思路：

与前边的组合，分割问题不同在于全排列问题每次递归至下一层后都要从头开始遍历。使用一个used数组进行去重，判断当前元素是否已经被使用

代码：

class Solution {
public:vector<vector<int>> result;vector<int> path;void backTracking(vector<int>& nums, vector<int>& used){if(path.size() == nums.size()) {result.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(used[i] == 0){used[i] = 1;path.push_back(nums[i]);backTracking(nums,used);path.pop_back();used[i] = 0;}}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<int> used(nums.size(), 0);backTracking(nums,used);return result;}
};

47.全排列 II

题目链接：. - 力扣（LeetCode）

讲解视频：

回溯算法求解全排列，如何去重？| LeetCode：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]]

解题思路：

先对nums数组排序，去重逻辑：

1. 横向去重：使用used数组对同层元素进行判断，若前后元素相同且前一个元素used值为0（表明当前遍历是同层遍历），就说明该元素已经被使用，跳过这个元素；
2. 纵向去重：每次递归至下一层后都要从头开始遍历。使用同一个used数组进行去重，判断当前元素是否已经被使用

代码：

class Solution {
public:vector<vector<int>> result;vector<int> path;void backTracking(vector<int>& nums,vector<int>& used){if(path.size() == nums.size()) {result.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0) continue;if(used[i] == 0){path.push_back(nums[i]);used[i] = 1;backTracking(nums,used);used[i] = 0;path.pop_back();}}}vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(),nums.end());vector<int> used(nums.size(),0);backTracking(nums,used);return result;}
};

51. N皇后

题目链接：. - 力扣（LeetCode）

讲解视频：

这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后

题目描述：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

解题思路：

N皇后问题步骤：

1. 按行遍历，对每一行中每一个位置做判断，看当前棋盘布局是否符合条件；
2. 判断标准：同一行，同一列，对角线（45°，135°）均不能存在2个及以上的Q；
3. 若所有行均遍历完成，就把结果保存至result中，并返回。

 

代码：

class Solution {
public:vector<vector<string>> result;bool isValid(vector<string>& chessboard, int row, int col, int n){for(int i = 0; i < row; i++) // 判断列if(chessboard[i][col] == 'Q') return false;for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--) //对角45°if(chessboard[i][j] == 'Q') return false;for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++) //对角135°if(chessboard[i][j] == 'Q') return false;return true;}void backTracking(vector<string>& chessboard, int row, int n){if(row == n){result.push_back(chessboard);return;}for(int col = 0; col < n; col++){if(isValid(chessboard,row,col,n)){chessboard[row][col] = 'Q';backTracking(chessboard,row+1,n);chessboard[row][col] = '.';}}}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n,string(n,'.'));backTracking(chessboard,0,n);return result;}
};

37. 解数独

题目链接：. - 力扣（LeetCode）

讲解视频：

回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独

题目描述：

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。题目数据 保证 输入数独仅有一个解

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

解题思路：

该题目与N皇后问题的区别在于：

1. 解数独问题中只要找到一个解即可，回溯函数类型为bool。N皇后问题找到所有解，回溯函数类型为void；
2. 解数独问题使用二维数组遍历。N皇后问题使用一维数组遍历。
3. 解数独问题中每一个格中从1~9中判断。N皇后问题每一个格只从Q判断
4. 解数独问题判断条件：同行同列不能有重复元素，3x3宫内不能有重复元素

代码：

class Solution {
public:bool isValid(int row, int col, int k, vector<vector<char>>& board){for(int i = 0; i < board[0].size(); i++) //判断行if(i != col && board[row][i] == k) return false; for(int i = 0; i < board.size(); i++) //判断列if(i != row && board[i][col] == k) return false; for(int i = row - row % 3; i < row - row % 3 + 3; i++)for(int j = col - col % 3; j < col - col%3 + 3; j++)if(i != row && j != col && board[i][j] == k) return false;return true;}bool backTracking(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 k = '1'; k <= '9'; k++){if(isValid(i,j,k,board)){board[i][j] = k;if(backTracking(board)) return true;board[i][j] = '.';}}return false;}}}return true;}void solveSudoku(vector<vector<char>>& board) {backTracking(board);}
};