模板
void dfs()//参数用来表示状态 { if(到达终点状态) { ...//根据题意添加 return; } if(越界或者是不合法状态) return; if(特殊状态)//剪枝 return ; for(扩展方式) { if(扩展方式所达到状态合法) { 修改操作;//根据题意来添加 标记； dfs（）； (还原标记)； //是否还原标记根据题意 //如果加上（还原标记）就是 回溯法 } } }
46. 全排列
class Solution { public: vector<vector<int>> res; vector<int> vis; vector<vector<int>> permute(vector<int>& nums) { vector<int> path; vis.resize(nums.size(), 0); dfs(nums, path, 0); return res; } void dfs(vector<int> & nums, vector<int>& path, int len){//参数表示状态 if(len == nums.size()){//递归出口 res.push_back(path);return; } for(int i = 0;i < nums.size(); i++){//扩展方式 if(vis[i] == 0){//扩展方式合法 path.push_back(nums[i]); vis[i] = 1; dfs(nums,path,len + 1); vis[i] = 0; path.pop_back(); } } } };
47. 全排列 II 排序去重
class Solution { public: vector<vector<int>> res; vector<int> vis; vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); vis.resize(nums.size(),0); vector<int> path; dfs(nums,path, 0); return res; } void dfs(vector<int>& nums, vector<int>& path, int depth){ if(depth == nums.size()){//递归出口 res.push_back(path); return; } for(int i = 0; i < nums.size(); i++){ //在同一深度只会遍历第一个相同的数字，不同深度时vis[i-1] = 1 if(i && nums[i] == nums[i-1] && vis[i-1] == 0) continue; if(vis[i] == 0){ vis[i] = 1; path.push_back(nums[i]); dfs(nums,path,depth + 1); vis[i] = 0; path.pop_back(); } } } };
491. 递增子序列
class Solution { public: vector<vector<int>> res; vector<int> vis; vector<vector<int>> findSubsequences(vector<int>& nums) { vis.resize(nums.size(),0); vector<int> path; dfs(nums,path,0); return res; } void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start if(path.size() >= 2){//过程状态也要记录 res.push_back(path); } if(start == nums.size()) return; unordered_set<int> mp;//去重 for(int i = start;i < nums.size(); i++){//扩展方式 //if(vis[i] == 0){这里不需要vis if((path.size() == 0 || nums[i] >= path.back()) && mp.count(nums[i]) == 0){ mp.insert(nums[i]); path.push_back(nums[i]); dfs(nums,path,i + 1);//这里别写错了 path.pop_back(); } } } };
39. 组合总和
元素可以重复利用且没有顺序，所以不要vis数组
class Solution { public: vector<vector<int>> res; vector<vector<int>> combinationSum(vector<int>& nums, int target) { vector<int> path; dfs(nums,path,0,target); return res; } void dfs(vector<int> &nums,vector<int>& path, int start, int target){ //出口 if(target < 0) return; if(target == 0){ res.push_back(path); return; } //遍历 for(int i = start; i <nums.size(); i++){ path.push_back(nums[i]); dfs(nums,path,i, target - nums[i]); path.pop_back(); } } };
40. 组合总和 II 比上题多了一个去重操作；
class Solution { public: vector<vector<int>> res; vector<vector<int>> combinationSum2(vector<int>& nums, int target) { sort(nums.begin(),nums.end());//加个去重操作 vector<int> path; dfs(nums,path,0,target); return res; } void dfs(vector<int> &nums,vector<int>& path, int start, int target){ //出口 if(target < 0) return; if(target == 0){ res.push_back(path); return; } //遍历 for(int i = start; i <nums.size(); i++){ if(i > start && nums[i] == nums[i-1] ) continue;//注意是i > start path.push_back(nums[i]); dfs(nums,path,i+1, target - nums[i]); // start = i + 1 path.pop_back(); } } };
78. 子集
class Solution { public: vector<vector<int>> res; vector<int> vis; vector<vector<int>> subsets(vector<int>& nums) { vis.resize(nums.size(),0); vector<int> path; dfs(nums,path,0); return res; } void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start res.push_back(path); if(start == nums.size()) return; for(int i = start;i < nums.size(); i++){//扩展方式 //似乎没条件 path.push_back(nums[i]); dfs(nums,path,i + 1);//这里别写错了 path.pop_back(); } } };
90. 子集 II 上题基础上加个去重
class Solution { public: vector<vector<int>> res; vector<int> vis; vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end());//排序便于去重 vis.resize(nums.size(),0); vector<int> path; dfs(nums,path,0); return res; } void dfs(vector<int> & nums, vector<int>& path, int start){//参数表示状态，从前往后，depth改为start res.push_back(path); if(start == nums.size()) return; for(int i = start;i < nums.size(); i++){//扩展方式 if(i > start && nums[i] == nums[i-1]) continue; //去重 path.push_back(nums[i]); dfs(nums,path,i + 1);//这里别写错了 path.pop_back(); } } };
进阶：N皇后问题
51. N皇后
class Solution { public: vector<vector<string>> res; vector<vector<string>> solveNQueens(int n) { string t = ""; for(int i = 0; i < n; i++) t += '.'; vector<string> path(n,t); vector<vector<int>> vis(n, vector<int>(n,0)); dfs(path,vis,n,0); return res; } void dfs(vector<string>& path,vector<vector<int>> &vis, int& n, int row){ if(row == n){//递归出口，前n行全部被赋值 res.push_back(path);return; } for(int j = 0; j < n; j++){//遍历一行 if(vis[row][j] == 0){//条件 path[row][j] = 'Q'; //注意，不能直接让vis变1和变0，否则后来的修改可能会改变原来的修改 for(int i = row; i < n; i++)vis[i][j]++;//该列 for(int i = row; i < n; i++){//对角线 if(j + i - row < n) vis[i][j + i - row]++; if(j + row - i >= 0) vis[i][j + row - i]++; } dfs(path, vis, n, row + 1); path[row][j] = '.'; for(int i = row; i < n; i++)vis[i][j]--;//该列 for(int i = row; i < n; i++){//对角线 if(j + i - row < n) vis[i][j + i - row]--; if(j + row - i >= 0) vis[i][j + row - i]--; } } } } };
37. 解数独
class Solution { public: int col[9][9] = {0}; int row[9][9] = {0}; int box[9][9] = {0}; void solveSudoku(vector<vector<char>>& board) { int n = board.size(); //初始化 for(int i = 0; i <9; i++) for(int j = 0; j < 9; j++){ if(board[i][j] != '.'){ int t = board[i][j] - '1'; col[j][t]++; row[i][t]++; box[i/3*3+ j/3][t]++; } } dfs(board, 0, 0); } //传参 int a[][9] 或者 int (*a)[9] 而不是 (int*)[9] a // box x/3*3 + y/3 而不是 x/3 + y/3; // (y + 1)%3 而不是 (++y)/3 bool dfs(vector<vector<char>>& board, int x, int y){ if(x == 9) return true;//递归出口 //特殊状态 if(board[x][y] != '.') return dfs(board,x + (y==8),(++y)%9); for(int k = 0; k < 9; k++){//遍历 //条件 if(row[x][k] || col[y][k] || box[x/3*3 + y/3][k]) continue; board[x][y] = k + '1'; row[x][k]++;col[y][k]++;box[x/3*3 + y/3][k]++; if(dfs(board,x + (y==8),(y + 1)%9)) return true;//找到一个解就退出 board[x][y] = '.'; row[x][k]--;col[y][k]--;box[x/3*3 + y/3][k]--; } return false; } };