代码随想录day25回溯算法4

文章目录

• 46.全排列
• 47.全排列 II
• 51. N 皇后

46.全排列

题目链接
文章讲解

class Solution {public: vector<vector<int>> ans; vector<int> path; bool f[1001]; void dfs(vector<int>& nums) { int n=nums.size(); if(path.size()==n) { ans.push_back(path); return ; } for(int i=0;i<n;i++) { if(f[i]==true) continue; path.push_back(nums[i]); f[i]=true; dfs(nums); f[i]=false; path.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { dfs(nums); return ans; }};

47.全排列 II

题目链接
文章讲解

class Solution {public: vector<vector<int>> ans; vector<int> path; bool f[1001]; void dfs(vector<int>& nums) { if(path.size()==nums.size()) { ans.push_back(path); return ; } unordered_set<int> se; for(int i=0;i<nums.size();i++) { if(se.find(nums[i])!=se.end()) continue; if(f[i]==true) continue; path.push_back(nums[i]); se.insert(nums[i]); f[i]=true; dfs(nums); f[i]=false; path.pop_back(); } } vector<vector<int>> permuteUnique(vector<int>& nums) { dfs(nums); return ans; }};

51. N 皇后

题目链接
文章讲解

class Solution {public: vector<vector<string>> ans; // 存储所有的解 // 检查在棋盘的 (row, col) 位置放置皇后是否是合法的 bool isvalid(int row, int col, int n, vector<string>& chess) { // 检查同一列是否已有皇后 for (int i = 0; i < n; i++) { if (chess[i][col] == \'Q\') return false; // 如果这一列有 \'Q\'，返回 false } // 检查同一行是否已有皇后 for (int i = 0; i < n; i++) { if (chess[row][i] == \'Q\') return false; // 如果这一行有 \'Q\'，返回 false } // 检查左上到右下对角线是否已有皇后 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chess[i][j] == \'Q\') return false; // 如果对角线有 \'Q\'，返回 false } // 检查右上到左下对角线是否已有皇后 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chess[i][j] == \'Q\') return false; // 如果对角线有 \'Q\'，返回 false } return true; // 如果没有违反任何规则，返回 true } // 回溯算法，用来寻找所有的合法解 void dfs(int n, int row, vector<string>& chess) { if (row == n) { // 如果已经填满所有行，说明找到了一个解 ans.push_back(chess); // 将当前棋盘状态添加到答案中 return; } // 尝试将皇后放置在第 row 行的每一列 for (int i = 0; i < n; i++) { if (isvalid(row, i, n, chess)) { // 如果该位置合法 chess[row][i] = \'Q\'; // 放置皇后 dfs(n, row + 1, chess); // 递归处理下一行 chess[row][i] = \'.\'; // 回溯，移除皇后，尝试其他可能的解 } } } // 主函数，用来返回所有的解 vector<vector<string>> solveNQueens(int n) { // 初始化一个n x n的棋盘，所有位置初始化为 \'.\' vector<string> chess(n, string(n, \'.\')); dfs(n, 0, chess); // 从第0行开始递归 return ans; // 返回所有解 }};