回溯算法
子集问题
①res,path; backtracking函数
②无递归终止条件判断，直接path存入res；
③递归需要startIndex；
④(补充)“有重复元素、不能包含重复的解集” 在for循环多加判断条件：i>0 && used[i-1]==false && nums[i]==nums[i-1] 跳过同层重复元素的处理
- 78. 子集
递归终止条件可以省略（与for循环的判断条件一致），每次递归调用的时候先把结果写入到res中 - 90. 子集 II
此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。其他没有什么强调的了。
78. 子集
递归终止条件可以省略（与for循环的判断条件一致），每次递归调用的时候先把结果写入到res中
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {res.push_back(path);for(int i=startIndex;i<nums.size();i++) {path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return res;}
};
90. 子集 II
此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums,int startIndex, vector<bool>& used) {res.push_back(path);for(int i=startIndex;i<nums.size();i++) {if(i>0 && used[i-1]==false && nums[i]==nums[i-1]) {continue;}path.push_back(nums[i]);used[i]=true;backtracking(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);backtracking(nums,0,used);return res;}
};
排列问题
全排列需要对所有元素进行排列，
①终止条件：path.size == nums.size()
②for遍历元素集合为所有元素，用used控制不重复
③有重复元素，要求解集不重复的处理条件：i>0 && nums[i]==nums[i-1] && used[i-1]==false
- 46. 全排列
排列问题，path写入res中一定是包含了nums的所有元素，只是排列顺序不同
遍历的元素集合为所有元素，只是需要used数组，标记已使用过的元素避免出现重复 - 47. 全排列 II
还是强调对于不重复解集的处理
46. 全排列
排列问题，path写入res中一定是包含了nums的所有元素，只是排列顺序不同
遍历的元素集合为所有元素，只是需要used数组，标记已使用过的元素避免出现重复
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, vector<bool>& used) {if(path.size()==nums.size()) {res.push_back(path);}for(int i=0;i<nums.size();i++) {if(used[i]==true)continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};
47. 全排列 II
还是强调对于不重复解集的处理
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, vector<bool>& used) {if(path.size()==nums.size()) {res.push_back(path);}for(int i=0;i<nums.size();i++) {if(used[i]==true) {continue;}else if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){continue;}path.push_back(nums[i]);used[i]=true;backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};
棋盘问题
需要定义棋盘（或题目给出），一层or两层循环（看题目逻辑），单独的isValid函数判断放置是否合理
①backtracking函数，棋盘选择按行递归或者逐元素递归
②isValid函数判断放置是否合理
- 51. N 皇后
1.构建棋盘 vector chessboard(n,string(n,‘.’));
2.逐行使用回溯，使用isValid函数判断放置位置是否合理
3.isValid函数，判断列、45度方向、135度方向放置是否合理 - 37. 解数独
1.双层循环，i j定位到要放数字的点，isValid判断是否符合逻辑，使用回溯递归调用
2.isValid判断行、列，以及内部小九格是否有重复数字
51. N 皇后
1.构建棋盘 vector chessboard(n,string(n,‘.’));
2.逐行使用回溯，使用isValid函数判断放置位置是否合理
3.isValid函数，判断列、45度方向、135度方向放置是否合理
class Solution {
public:vector<vector<string>> res;void backtracking(int n,int row,vector<string>& chessboard) {if(row == n) {res.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;}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n,string(n,'.'));backtracking(n,0,chessboard);return res;}
};
37. 解数独
1.双层循环，i j定位到要放数字的点，isValid判断是否符合逻辑，使用回溯递归调用
2.isValid判断行、列，以及内部小九格是否有重复数字
class Solution {
public: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 c = '1';c<='9';c++) {if(isValid(i,j,c,board)) {board[i][j]=c;if(backtracking(board)) {return true;}board[i][j]='.';}}return false;}}}return true;}bool isValid(int row,int col,char k,vector<vector<char>>& board) {for(int i=0;i<9;i++) {if(board[row][i] == k)return false;}for(int i=0;i<9;i++) {if(board[i][col] == k)return false;}int row_1 = (row/3)*3;int col_1 = (col/3)*3;for(int i=row_1;i<row_1+3;i++) {for(int j=col_1;j<col_1+3;j++) {if(board[i][j]==k)return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};
