1全排列 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]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
思路：
这道题目和46.全排列 的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。
这里又涉及到去重了。
1. 递归函数的返回值以及参数
返回值和参数：
void backtracking(vector<int>& nums, vector<bool>& used)- 返回值为
void，因为每次调用只需要修改全局变量path和result，不需要从函数中返回特定值。 - 参数
nums是输入的原始数组，used是一个标记数组，用于记录每个位置的元素是否已经被使用过。
- 返回值为
2. 回溯函数的终止条件
终止条件：
if (path.size() == nums.size())- 当
path的长度等于nums的长度时，表示已经形成了一个完整的排列，将path加入到result中，并返回。
- 当
3. 单层搜索的过程
解题思路：
- 选择路径： 每次递归调用时，在未使用过的元素中选择一个加入到
path中。 - 判断条件： 使用
used数组来判断当前元素是否已经被使用过，以及是否需要去重。 - 标记和递归：
- 将当前未使用的元素加入
path中，并标记为已使用。 - 递归调用
backtracking，继续向下一层搜索。 - 在递归返回后，执行回溯操作：撤销选择，恢复标记状态，以便进行下一次选择。
- 将当前未使用的元素加入
去重部分
去重条件：
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == true)- 当前元素与上一个元素相同，并且上一个元素已经被使用过时，跳过当前元素，避免重复选择相同的元素。
代码：
#include <vector>
#include <algorithm> // 包含排序函数 sort
using namespace std;
class Solution {
private:
vector<int> path; // 存储当前路径的一维向量
vector<vector<int>> result; // 存储最终结果的二维向量
// 回溯函数，参数为原始数组nums和标记数组used
void backtracking(vector<int>& nums, vector<bool>& used) {
// 当路径长度等于数组长度时，将当前路径加入结果集合
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
// 遍历数组nums
for (int i = 0; i < nums.size(); i++) {
// 如果元素已经被使用过，则跳过
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == true) {
continue; // 去重部分：跳过重复的元素
}
if (used[i] == true) {
continue; // 如果元素已经被使用过，则跳过
}
// 标记当前元素为已使用
used[i] = true;
// 将当前元素加入路径中
path.push_back(nums[i]);
// 递归进入下一层决策树
backtracking(nums, used);
// 回溯操作，撤销选择
used[i] = false;
path.pop_back();
}
}
public:
// 主函数，生成所有排列的入口函数
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear(); // 清空结果集合
path.clear(); // 清空当前路径
sort(nums.begin(), nums.end()); // 排序输入数组，确保重复元素相邻
vector<bool> used(nums.size(), false); // 标记数组，记录每个位置的元素是否被使用过
// 调用回溯函数，从第一个位置开始生成排列
backtracking(nums, used);
// 返回最终的结果集合
return result;
}
};2 N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9
思路：
1. 递归函数的返回值以及参数
递归函数 backtracking 的目的是在棋盘上逐行放置皇后，并检查每一步是否符合规则。其参数包括 int n（棋盘大小），int row（当前处理的行数），vector<string>& chessboard（当前棋盘状态）。它没有显式的返回值，而是通过修改全局变量 result 来存储所有合法的解。
2. 回溯函数终止条件
在 backtracking 函数中，终止条件是当 row 等于 n 时，即所有行都处理完毕，此时找到了一个合法的皇后布局，将其加入 result 数组中。
if (row == n) {
result.push_back(chessboard); // 找到一种解法，存入结果
return;
}
3. 单层搜索的过程
在每一层递归中，通过循环尝试将皇后放置在当前行的每一个列上，然后递归处理下一行。在尝试放置之前，通过 isValid 函数检查当前位置是否合法，避免皇后之间的冲突。
for (int col = 0; col < n; col++) {
if (isValid(row, col, chessboard, n)) {
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard); // 递归处理下一行
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
这种方法通过逐行放置皇后，并通过回溯撤销不符合条件的放置，最终找到所有合法的N皇后布局。
代码：
class Solution {
private:
vector<vector<string>> result; // 存放最终的结果
// 回溯算法核心函数
// n 是棋盘大小，row 是当前递归到的行数，chessboard 是当前的棋盘状态
void backtracking(int n, int row, vector<string>& chessboard) {
// 如果已经递归到最后一行，说明找到了一种解法，将其存入结果集合中
if (row == n) {
result.push_back(chessboard);
return;
}
// 遍历当前行的每一列，尝试放置皇后
for (int col = 0; col < n; col++) {
// 检查当前位置是否可以放置皇后
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard); // 递归处理下一行
chessboard[row][col] = '.'; // 回溯，撤销皇后
}
}
}
// 检查当前位置是否可以放置皇后
bool isValid(int row, int col, vector<string>& chessboard, 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--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查右上方是否有皇后冲突
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear(); // 清空结果集
vector<string> chessboard(n, string(n, '.')); // 初始化棋盘，全部用'.'表示空
backtracking(n, 0, chessboard); // 从第一行开始递归求解
return result; // 返回所有解法
}
};3. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
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"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
思路：
1. 递归函数的返回值与参数
递归函数 backtracking 的目标是填充数独中的空白格子（用’.'表示），使得每个数字都符合数独的规则（每行、每列、每个3x3子数独内都不能有重复的数字）。具体来说：
- 参数： 函数接受一个二维字符数组
board，即数独的当前状态。 - 返回值： 返回一个布尔值，表示是否找到了符合规则的解（找到解返回
true，否则返回false）。
2. 回溯函数的终止条件
在 backtracking 函数中，回溯的终止条件包括：
- 当找到一个空白格子（‘.’）时，尝试填入数字’1’到’9’。
- 对于每个尝试的数字，使用
isValid函数检查其在当前位置是否符合数独规则。 - 如果找到一个有效的数字，则将其放入当前格子中，并递归地调用
backtracking继续填充下一个空白格子。 - 如果当前尝试的数字不能使得数独的解合法，则撤销当前的选择（回溯），尝试下一个数字。
3. 单层搜索的过程（解题思路）
在单层搜索的过程中：
- 遍历数独的每个格子，对于每个空白格子尝试填入数字’1’到’9’。
- 使用
isValid函数来检查填入的数字是否在当前行、当前列和当前3x3子数独内都没有重复出现。 - 如果找到一个合法的填入方式，则继续递归填充下一个空白格子；如果找不到合法的填入方式，则进行回溯。
- 当所有空白格子都被填满且符合数独规则时，数独问题得到解决。
判断一个数独棋盘是否合法，主要依据以下三个维度进行检查：
-
同行是否重复：
- 对于每一行，检查其中的每个数字是否唯一。遍历每一行，使用一个集合或者数组来记录已经出现过的数字，若再次出现相同数字则表示该行不合法。
-
同列是否重复：
- 对于每一列，检查其中的每个数字是否唯一。遍历每一列，同样使用集合或数组记录已经出现过的数字，如果重复出现则该列不合法。
-
9宫格是否重复：
- 数独棋盘被分为9个3x3的子宫格。对于每个子宫格，检查其中的数字是否唯一。通过计算当前位置所在的子宫格的起始行和起始列（使用
(row / 3) * 3和(col / 3) * 3计算），遍历该子宫格内的所有数字，同样使用集合或数组来记录已经出现过的数字，若有重复则该子宫格不合法。
- 数独棋盘被分为9个3x3的子宫格。对于每个子宫格，检查其中的数字是否唯一。通过计算当前位置所在的子宫格的起始行和起始列（使用
代码：
class Solution {
private:
// 回溯函数，尝试解决数独问题
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] == '.') {
// 尝试填充数字1到9
for(char k = '1'; k <= '9'; k++) {
// 如果当前数字k在位置(i, j)合法
if(isValid(i, j, k, board)) {
board[i][j] = k; // 放置数字k
// 递归调用backtracking，尝试填充下一个空白格
if(backtracking(board)) return true;
board[i][j] = '.'; // 回溯，撤销当前位置的填充
}
}
return false; // 1-9都尝试过，无解
}
}
}
return true; // 数独已解
}
// 检查在位置(row, col)填充字符val是否合法
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
// 检查同一行是否有重复
for(int i = 0; i < 9; i++) {
if(board[row][i] == val) {
return false;
}
}
// 检查同一列是否有重复
for(int j = 0; j < 9; j++) {
if(board[j][col] == val) {
return false;
}
}
// 检查同一个3x3子数独内是否有重复
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; // 合法
}
public:
// 解决数独问题的入口函数
void solveSudoku(vector<vector<char>>& board) {
backtracking(board); // 调用回溯函数解决数独
}
};
