491. 非递减子序列
思路：这道题要求求递增的子序列，所以需要判断两个东西，一个是这个后面的元素比前面的元素大，且子序列中元素个数大于等于2，其他逻辑与之前一样，用数组来对树层之间进行去重。
我的代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracing(vector<int>& nums,int startIndex) {
if(path.size()>1) {
result.push_back(path);
}
int used[201]={0};
for(int i=startIndex;i<nums.size();i++) {
if((!path.empty()&&nums[i]<path.back())||used[nums[i]+100]) continue;
used[nums[i]+100]=1;
path.push_back(nums[i]);
backtracing(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracing(nums,0);
return result;
}
};
46. 全排列
思路：排列和组合的区别就是12和21是两个不同的排列，所以这里startIndex就不用了，每一次都要从第一个元素开始遍历，但是选过的元素不能再选一遍，即需要used数组来进行去重，其他过程与之前的题目一样。
我的代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracing(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]) continue;
path.push_back(nums[i]);
used[i]=1;
backtracing(nums,used);
path.pop_back();
used[i]=0;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> used(nums.size(),0);
backtracing(nums,used);
return result;
}
};
47. 全排列 II
思路：这道题目就是将之前组合的去重逻辑搬到这道题目再结合上一道题目的排列的思路即可。
我的代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracing(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]) continue;
if(!used[i]) {
path.push_back(nums[i]);
used[i]=1;
backtracing(nums,used);
path.pop_back();
used[i]=0;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> used(nums.size(),0);
sort(nums.begin(),nums.end());
backtracing(nums,used);
return result;
}
};
51. N 皇后
思路：首先这题需要一个判断皇后位置是否合法的函数，然后用for循环对每一列进行遍历，再用递归对每一行进行遍历，当行数为题目所给的时候，就说明找到了一种N皇后的组合方式，加入结果数组中返回就可以了。
我的代码：
class Solution {
private:
vector<vector<string>> result;
bool isvalid(int col,int row,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;
}
void backtracking(vector<string>& chessboard,int row,int n) {
if(row==n) {
result.push_back(chessboard);
return;
}
for(int i=0;i<n;i++) {
if(isvalid(i,row,chessboard,n)) {
chessboard[row][i]='Q';
backtracking(chessboard,row+1,n);
chessboard[row][i]='.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> chessboard(n,string(n,'.'));
backtracking(chessboard,0,n);
return result;
}
};
37. 解数独
思路：这道题目需要打破固化思维，需要用“二维递归”用多个for循环，遍历每行每列，再用递归遍历1-9每个数字是否可以，找到一个可以的结果就直接返回，所以递归函数用bool类型，而判断是否合法需要判断每行和每列是不是有这个数字，还有这个九宫格中是不是有这个数字。注意再九宫格判断的时候startrow和col计算公式是
int startrow=(row/3)*3;
int startcol=(col/3)*3;
乍一看好像什么都没做，但是这里除法是取整的，所以这个操作实际上是将其定位在这个数字所在行和列的那个九宫格的起始位置。
我的代码：
class Solution {
private:
bool isvalid(int row,int col,int 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;
}
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;
}
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;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
今日总结
今天回溯算法就正式完结了，大总结可以参考：回溯总结|代码随想录
今天的N皇后和解数独还是很有难度的，需要理解他判断是否合法的逻辑，以及递归和回溯的逻辑，还需要思考他的时间复杂度和空间复杂度，剪枝带来的效果对时间复杂度的影响等等。不过按照回溯专题层层递进的难度梯度，理解起来还是可以的，每天进入新章节，加油！
