[TOC]
岛屿系列算法问题是经典的面试高频题，岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。
如何在二维矩阵中使用 DFS 搜索呢？
可以把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。
因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路
// 从(i, j)出发，向相邻四个方向搜索
void dfs(vector<vector<int>>& grid,int i,int j, vector<vector<bool>>& visited) {
int m = grid.length, n = grid[0].length;
// 如果超出索引边界，返回
if (i < 0 || j < 0 || i >= m || j >= n) return;
// 如果已遍历过 (i, j)，返回
if (visited[i][j]) return;
// 进入节点 (i, j)
visited[i][j] = true;// 标记当前点已经访问过
dfs(grid, i - 1, j, visited); // 向上搜索
dfs(grid, i + 1, j, visited); // 向下搜索
dfs(grid, i, j - 1, visited); // 向左搜索
dfs(grid, i, j + 1, visited); // 向右搜索
}
1、组合问题
494. 目标和（中等难度）
给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ，求运算结果等于 target 的不同 表达式 的数目。
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
点评
该题目提交可能会超时，尝试多次提交
class Solution {
public:
int res=0;
void dfs(vector<int>& nums, int target,int index,int sum){
if(index==nums.size()){
if(sum==target) res++;
return;
}
// nums[startIndex]尝试+
sum+=nums[index];
dfs(nums, target, index+1,sum);
sum-=nums[index];
// nums[startIndex]尝试-
sum-=nums[index];
dfs(nums, target, index+1,sum);
sum+=nums[index];
}
int findTargetSumWays(vector<int>& nums, int target) {
dfs(nums, target, 0, 0);
return res;
}
};
77. 组合（中等难度）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
点评：
从非重序列中找出所有的非重组合：
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(int n, int k,int startIndex){
if(path.size()==k){
res.push_back(path);
return;
}
for(int i=startIndex;i<=n;++i){
path.push_back(i);
dfs(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
dfs(n,k,1);
return res;
}
};
39. 组合总和（中等难度）
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
点评：
从非重序列中找出所有目标和为target的非重组合。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums, int target,int sum,int startIndex){
if(sum==target){
res.push_back(path);
return;
}
if(sum>target){
return;
}
for(int i=startIndex;i<nums.size();++i){
path.push_back(nums[i]);
sum+=nums[i];
dfs(nums,target,sum,i);
path.pop_back();
sum-=nums[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates,target,0,0);
return res;
}
};
40. 组合总和 II（中等难度）
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
点评：
从含重序列中找出所有目标和为target的非重组合。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums, int target,int sum,int startIndex,vector<bool>& used){
if(sum==target){
res.push_back(path);
return;
}
if(sum>target){
return;
}
for(int i=startIndex;i<nums.size();++i){
if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) continue;
used[i]=true;
path.push_back(nums[i]);
sum+=nums[i];
dfs(nums,target,sum,i+1,used);
path.pop_back();
sum-=nums[i];
used[i]=false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<bool> used(candidates.size(), false);
dfs(candidates,target,0,0,used);
return res;
}
};
216. 组合总和 III（中等难度）
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
点评：
从非重序列中找出所有目标和为target且个数为k的非重组合。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(int k, int n,int startIndex,int sum,int num){
if(sum>n||num>k){
return;
}
if(sum==n&&num==k){
res.push_back(path);
return;
}
for(int i=startIndex;i<=9;++i){
path.push_back(i);
sum+=i;
num++;
dfs(k,n,i+1,sum,num);
path.pop_back();
sum-=i;
num--;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k,n,1,0,0);
return res;
}
};
17. 电话号码的字母组合（中等难度）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
点评：
从多个不同的字符串中分别取一个字母，问有多少种组合？
class Solution {
public:
unordered_map<char,string> dict;
vector<string> res;
string path;
void dfs(string& digits,int startIndex){
if(startIndex==digits.size()){
res.push_back(path);
return;
}
// 遍历每个节点
string str=dict[digits[startIndex]];
for(int i=0;i<str.length();++i){
path.push_back(str[i]);
dfs(digits,startIndex+1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
dict['2']="abc";
dict['3']="def";
dict['4']="ghi";
dict['5']="jkl";
dict['6']="mno";
dict['7']="pqrs";
dict['8']="tuv";
dict['9']="wxyz";
if(digits=="") return res;
dfs(digits,0);
return res;
}
};
2、子集问题
78. 子集（中等难度）
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
点评：
从非重序列中找所有的非重子集
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
// 从nums的剩余序列[startIndex,:]中取
void dfs(vector<int>& nums, int startIndex){
res.push_back(path);
// 当剩余集合为空时，返回
if (startIndex >= nums.size()) return;
// 从剩余序列[startIndex,:]中取数字
for(int i =startIndex; i <nums.size(); ++i) {
path.push_back(nums[i]);// 添加剩余序列的第一个数字
dfs(nums, i+1);// 下一层，剩余序列变小
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return res;
}
};
90. 子集 II（中等难度）
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
点评：
从含重序列中找所有的非重子集
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums,int startIndex,vector<bool>& used){
res.push_back(path);
if(startIndex>=nums.size()) return;
// 遍历树的节点
for(int i=startIndex;i<nums.size();++i){
// 如果同层取值相同则跳过
if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) continue;
// 同层不同
used[i]=true;
path.push_back(nums[i]);
dfs(nums,i+1,used);
path.pop_back();
used[i]=false;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(), false);
dfs(nums, 0,used);
return res;
}
};
491. 递增子序列（中等难度）
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums,int startIndex){
if(path.size()>=2) {
res.push_back(path);
//return;
}
// 是否添加nums[i]
unordered_set<int> uset;// 使用set对本层元素进行去重
for(int i=startIndex;i<nums.size();++i){
// 如果当前添加元素nums[i]<上一个元素，跳过
if(!path.empty()&&nums[i]<path.back()) continue;
// 相邻元素去重
//if(i>startIndex&&nums[i]==nums[i-1]) continue;
// 非相邻元素去重
if(uset.count(nums[i])) continue;
uset.insert(nums[i]);
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(nums,0);
return res;
}
};
698. 划分为k个相等的子集（中等难度）
点评
将若干个球放入若干个桶的问题
class Solution {
public:
// 将多个球nums放入k个容量为target的桶buckets,是否存在分法，index : 第 index 个球开始做选择
bool dfs(vector<int>& nums,vector<int>& buckets,int index){
// 如果所有的球已经分完，返回true
if(index>=nums.size()) return true;
// 第index个球nums[index] 开始做选择，放入桶buckets[i]（共有k个桶）
for(int i=0; i<buckets.size();++i){
if(nums[index]>buckets[i]) continue; //如果当前数字大于桶的容量，跳过
if(i>0&&buckets[i]==buckets[i-1]) continue; // 如果该桶和上一个桶容量相同，跳过
buckets[i]-=nums[index];//放入桶buckets[i]，容量减少
// 下一个球开始选择，如果返回true，说明当前分法可行
if(dfs(nums,buckets,index+1)) return true;
buckets[i]+=nums[index]; //撤销
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum=0;
sort(nums.rbegin(),nums.rend());// 从大到小排序（必须，否则会超时）
for(int n:nums)sum+=n;
if(sum%k!=0) return false; // 如果数组和无法被k整除则肯定无法划分
// 回溯
int target=sum/k;
vector<int> buckets(k,target);//定义k个桶,每个桶的容量为target
return dfs(nums,buckets,0);
}
};
473. 火柴拼正方形（中等难度）
3、排列问题
46. 全排列（中等难度）
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。
点评：
从非重序列中找到所有
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums,vector<bool>& used){
// 达到决策树的底部，此时used全部为true
if(path.size()==nums.size()){
res.push_back(path);
return;
}
// 遍历决策树的每个节点的所有分支
for(int i=0;i<nums.size();++i){
// 如果该路径中使用过nums[i],跳过
if(used[i]) continue;
// 标记正在使用nums[i]
used[i]=true;
path.push_back(nums[i]);
// 向下遍历
dfs(nums,used);
// 撤销标记
path.pop_back();
used[i]=false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
dfs(nums,used);
return res;
}
};
47. 全排列 II（中等难度）
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
点评：
和46相比，该题要求结果中不能包含重复的排列，由于该题的nums中包含重复数字，所以其会导致重复排列
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums,vector<bool>& used){
// 达到决策树的底部，此时used全部为true
if(path.size()==nums.size()){
res.push_back(path);
return;
}
// 遍历决策树的每个节点的所有分支
for(int i=0;i<nums.size();++i){
// 如果该路径中使用过nums[i],跳过
if(used[i]) continue;
// 如果nums[i]==nums[i-1],并且同一树层nums[i - 1]使用过，跳过
if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
// 进入该节点
used[i]=true;// 标记正在使用nums[i]
path.push_back(nums[i]);
dfs(nums,used);// 向下遍历
path.pop_back();// 撤销标记
used[i]=false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 排序
dfs(nums,used);
return res;
}
};
剑指 Offer 38. 字符串的排列（中等难度）
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
点评：
从一个含重序列中查找一个非重排列
class Solution {
public:
vector<string> res;
string path;
void dfs(string& s,vector<bool>& visited){
if(path.size()==s.length()){
res.push_back(path);
return;
}
for(int i=0;i<s.length();++i){
if(visited[i]) continue;
if(i>0&&s[i]==s[i-1]&&!visited[i-1]) continue;
path.push_back(s[i]);
visited[i]=true;
dfs(s,visited);
path.pop_back();
visited[i]=false;
}
}
vector<string> permutation(string s) {
vector<bool> visited(s.length(),false);
sort(s.begin(),s.end());
dfs(s,visited);
return res;
}
};
31. 下一个排列（中等难度）
class Solution {
public:
/* 本题的题意：将数组中的数进行排列，得到多个数组，然后将多个数组排序
找出这个数组排序出的所有数中，刚好比当前数大的那个数
难点在于必须原地修改
思路：从后向前遍历数组,保证i<j,找到第一个比nums[j]小的数，交换两个数，排序[i+1,:]
*/
void nextPermutation(vector<int>& nums) {
// 从后向前遍历，当前为i
for (int i = nums.size() - 1; i >= 0; i--) {
// 从后向前遍历,当前为j，保证j>i
for (int j = nums.size() - 1; j > i; j--) {
// 从后向前找到第一个比nums[j]小的数
if (nums[j] > nums[i]) {
swap(nums[j], nums[i]);//交换2个数
// 排序[i+1,:]
sort(nums.begin() + i + 1, nums.end());
return;
}
}
}
// 到这里了说明整个数组都是倒叙了，反转一下便可
reverse(nums.begin(), nums.end());
}
};
4、括号问题
22. 括号生成（中等难度）
剑指 Offer II 085. 生成匹配的括号（中等难度）
面试题 08.09. 括号（中等难度）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
点评：
第一个「合法」的括号字符串一定满足如下2个条件：
1、括号字符串中的左括号数量一定等于右括号数量。
2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
在回溯遍历时，检查其左右括号的数量
class Solution {
public:
vector<string> res;
string path;
// 左括号的数量、右括号的数量
void dfs(int n,int left,int right){
if(right>left) return;// 从左向右添加括号字符，当右括号多的时候就一定不符合
if(left>n||right>n) return;// 如果有某个括号超过一半，则一定不是合法的
// 如果左右括号恰好都为n
if(left==n&&right==n){
res.push_back(path);
return ;
}
// 先尝试放入左括号
path.push_back('(');
dfs(n,left+1,right);
path.pop_back();
// 再尝试放入右括号
path.push_back(')');
dfs(n,left,right+1);
path.pop_back();
}
vector<string> generateParenthesis(int n) {
dfs(n,0,0);
return res;
}
};
301. 删除无效的括号（困难难度）
这道题和1249的区别在于，1249题只返回最少需要移除的括号数量，即找出所有不匹配的括号位置即可。
该题要返回所有最好删除的括号数量的情况，这就有点复杂，因为我们搜索的不匹配的括号位置数量和
class Solution {
public:
vector<string> res;
vector<string> removeInvalidParentheses(string s) {
int lremove = 0;// 需要删除的左括号数量
int rremove = 0;// 需要删除的右括号数量
// 遍历字符串，统计要删除的左括号和右括号的数量
for (char c : s) {
if (c == '(') lremove++;
else if (lremove != 0&&c == ')') lremove--;
else if (lremove == 0&&c == ')') rremove++;// 要删除的右括号
}
dfs(s, 0, lremove, rremove);
return res;
}
void dfs(string& str, int start, int lremove, int rremove) {
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.size()) return;
// 如果左括号和右括号正好删够，并且是合法字符串
if (lremove == 0 && rremove == 0&&isValid(str)) {
res.push_back(str);
return;
}
// 每个节点从str的[start,:)，尝试分别删除左右括号
for (int i = start; i < str.size(); i++) {
// 如果同一层分支相同，则直接跳过
if (i>start && str[i] == str[i - 1]) continue;
// 假如要删除
// 尝试去掉一个左括号
if ( str[i] == '(') {
string tmp=str.substr(0, i)+str.substr(i + 1);
dfs(tmp, i, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if ( str[i] == ')') {
string tmp=str.substr(0, i)+str.substr(i + 1);
dfs(tmp, i, lremove, rremove - 1);
}
}
}
inline bool isValid(const string & s) {
int cnt = 0;
// 判断括号字符串是否合法
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
cnt++;
} else if (s[i] == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
};
5、分割问题
131. 分割回文串（中等难度）
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
class Solution {
public:
vector<vector<string>> res;
vector<string> path;
void dfs (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
res.push_back(path);
return;
}
// 从剩余字符串[startIndex,：]中去选取若干个子串
for (int i = startIndex; i < s.size(); i++) {
if(!isPalindrome(s, startIndex, i)) continue;
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
dfs(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程，弹出本次已经填在的子串
}
}
vector<vector<string>> partition(string s) {
dfs(s, 0);
return res;
}
// 判断是否是回文字符串
bool isPalindrome(const string& s, int start, int end) {
int i = start;int j = end;
while(i<j){
if (s[i++] != s[j--]) return false;
}
return true;
}
};
93. 复原 IP 地址（中等难度）
剑指 Offer II 087. 复原 IP（中等难度）
输入一个完全由数字组成的字符串，向其中添加 '.' 分隔使其变成一个有效 IP 地址 （正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0）），输出所有的分割方案。
输入：s = “101023” 输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
class Solution {
public:
vector<string> res;
vector<string> path;
void dfs(string& s,int startIndex){
int len=path.size();
if(len>4) return;
if(len == 4 && startIndex == s.size()) {
string str;
for(string s:path){
str+=s;
str+=".";
}
res.push_back(str.substr(0,str.length()-1));
return;
}
// 分别取s的不同长度的子串[startIndex,i]
for(int i=startIndex;i<s.size();++i){
string str=s.substr(startIndex,i-startIndex+1);// 此时的子串
//判断 [startIndex,i] 这个区间的子串是否合法
if (!isValid(str)) continue; //
path.push_back(str);
dfs(s, i+1); // 插入逗点之后下一个子串的起始位置为i+2
path.pop_back();
}
}
vector<string> restoreIpAddresses(string s) {
if (s.size() > 12) return res; // 算是剪枝了
dfs(s, 0);
return res;
}
// 判断一个字符串组织的函数是否合法
bool isValid(const string& str) {
int len=str.length();
if(len==0|| len > 3 ) return false;
if(len > 1 && str[0]=='0') return false;
int a=stoi(str);
if(a>255) return false;
return true;
}
};
6、棋盘问题
37. 解数独（困难难度）
class Solution {
public:
// 从board[i][j]开始搜索，找
bool dfs(vector<vector<char>>& board,int i,int j) {
// 找到一个可行解，触发 base case
if (i == 9) return true;
// 穷举到最后一列的话就换到下一行重新开始
if (j == 9) return dfs(board, i + 1, 0);
// 如果该位置是预设的数字，不用我们操心
if (board[i][j] != '.') return dfs(board, i, j + 1);
// 分别尝试在board[i][j]放1-9的数
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
// 如果遇到不合法的数字，跳过
if (!isValid(board,i, j, k)) continue;
// 合法数字填入
board[i][j] = k; // 放置k
if(dfs(board,i,j+1)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
// 穷举完 1~9，依然没有找到可行解，此路不通
return false;
}
void solveSudoku(vector<vector<char>>& board) {
dfs(board,0,0);
}
// 判断 board[i][j] 是否可以填入 val
bool isValid(vector<vector<char>>& board, int row, int col, char val) {
for (int i = 0; i < 9; i++) {
// 判断行是否存在重复
if (board[row][i] == val) return false;
// 判断列是否存在重复
if (board[i][col] == val) return false;
// 判断 3 x 3 方框是否存在重复
if (board[(row/3)*3 + i/3][(col/3)*3 + i%3] == val)
return false;
}
return true;
}
};
51. N 皇后（困难难度）
面试题 08.12. 八皇后（困难难度）
52. N皇后 II（困难难度）
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
PS：皇后可以攻击同一行、同一列、左上、左下、右上、右下共计8个方向的任意单位。
点评：
class Solution {
public:
vector<vector<string>> res;
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void dfs(vector<string>& grid,int row){
// 如果行数已经超过棋盘
if (row == grid.size()) {
res.push_back(grid);// 添加本次gird
return;
}
int n = grid[row].size();
// 在棋盘的第row行，尝试不同列
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(grid, row, col)) continue;
// 尝试放在第col列
grid[row][col] = 'Q';
// 进入下一行决策
dfs(grid, row + 1);
// 撤销选择
grid[row][col] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
vector<string> board(n, string(n, '.'));
dfs(board, 0);
return res;
}
/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector<string>& board, int row, int col) {
int n = board.size();
// 检查正上方是否有皇后互相冲突
for (int i = 0; i <= row; i++) {
if (board[i][col] == 'Q')return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};
####