DFS：深搜+回溯+剪枝实战解决OJ问题

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一  排列、子集问题

1.1  全排列I

1.2  子集I 

 1.3  找出所有子集的异或总和

1.4  全排列II

1.5  字母大小写全排列

1.6  优美的排列

二  组合问题 

2.1  电话号码的数字组合

 2.2  括号生成

2.3  组合 

2.4  目标和

2.5  组合总和

三  矩阵搜索问题

3.1  N皇后 

3.2  有效的数独

3.3  解数独 

3.4  单词搜素

3.5  黄金矿工

3.6  不同路径III

总结

---

前言

本篇详细介绍了进一步介绍DFS，让使用者对DFS有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

---

我们在做DFS的题目时，首先要把决策树（通过策略把结果不重不漏的枚举得到）画下，缕清思路，设计代码自然水到渠成

一  排列、子集问题

1.1  全排列I

46. 全排列 - 力扣（LeetCode）

 

class Solution {vector<vector<int>> ret;vector<int> path;bool check[7];
public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0;i<nums.size();i++){if(check[i] == false){path.push_back(nums[i]);check[i] = true;dfs(nums);//回溯-> 恢复现场path.pop_back();check[i] = false;}}}
};

1.2  子集I 

78. 子集 - 力扣（LeetCode）

解法一：

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int n){if(n == nums.size()){ret.push_back(path);return;}//选path.push_back(nums[n]);dfs(nums,n+1);path.pop_back();//不选dfs(nums,n+1);}
};

解法二：

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i = pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}
};

 1.3  找出所有子集的异或总和

1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）

 

class Solution {int sum;int path;
public:int subsetXORSum(vector<int>& nums) {dfs(nums,0);return sum;}void dfs(vector<int>& nums,int pos){sum += path;for(int i = pos;i<nums.size();i++){path^=nums[i];dfs(nums,i+1);path^=nums[i];       }}
};

1.4  全排列II

47. 全排列 II - 力扣（LeetCode）

 

class Solution {vector<vector<int>> ret;vector<int> path;bool check[9];
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0;i<nums.size();i++){if(check[i] == false && (i==0 || nums[i] != nums[i-1] ||check[i-1] == true)){path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back();check[i] = false;}}}
};

1.5  字母大小写全排列

784. 字母大小写全排列 - 力扣（LeetCode）

class Solution {vector<string> ret;string path;
public:vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s,int pos){if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];//不改变path += ch;dfs(s,pos+1);path.pop_back();//改变if(ch<'0' || ch>'9'){char tmp = change(ch);path += tmp;dfs(s,pos+1);path.pop_back();}}char change(char ch){if(ch>='a'&&ch<='z')    ch-=32;else    ch+=32;return ch;}
};

1.6  优美的排列

526. 优美的排列 - 力扣（LeetCode）

class Solution {bool check[16];int ret;
public:int countArrangement(int n) {dfs(n,1);return ret;}void dfs(int n, int pos){if(pos == n+1){ret++;return;}for(int i = 1; i<=n;i++){if(check[i] == false&&(i % pos == 0 || pos % i == 0)){check[i] = true;dfs(n,pos+1);check[i] = false;}}}
};

二  组合问题 

2.1  电话号码的数字组合

17. 电话号码的字母组合 - 力扣（LeetCode）

 

class Solution {string path;vector<string> ret;vector<string> hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:vector<string> letterCombinations(string digits) {if(digits.size() == 0)    return ret;dfs(digits,0);return ret;}void dfs(string digits,int pos){if(pos == digits.size()){ret.push_back(path);return;}for(auto& ch : hash[digits[pos] - '0']){path.push_back(ch);dfs(digits,pos+1);path.pop_back();}}
};

 2.2  括号生成

22. 括号生成 - 力扣（LeetCode）

class Solution {vector<string> ret;string path;int count; //记录有效括号的对数
public:vector<string> generateParenthesis(int n) {count = n;dfs(0,0);return ret;}void dfs(int left,int right){if(path.size() == 2*count){ret.push_back(path);return;}if(left<count){path.push_back('(');dfs(left+1,right);path.pop_back();}if(right<left){path.push_back(')');dfs(left,right+1);path.pop_back();}}
};

2.3  组合 

77. 组合 - 力扣（LeetCode）

 

class Solution {vector<vector<int>> ret;vector<int> path;int n, k;
public:vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs(1);return ret;}void dfs(int pos){if(path.size() == k){ret.push_back(path);return;}for(int i = pos; i<=n; ++i){path.push_back(i);dfs(i+1);path.pop_back();}}
};

2.4  目标和

494. 目标和 - 力扣（LeetCode）

class Solution {int ret;int target;
public:int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums, int pos, int prev){if(pos == nums.size()){if(prev == target)ret++;return;}dfs(nums,pos+1,prev+nums[pos]);dfs(nums,pos+1,prev-nums[pos]);}
};

2.5  组合总和

39. 组合总和 - 力扣（LeetCode）

解法一：

class Solution {vector<vector<int>> ret;vector<int> path;int target;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int sum, int pos){if(sum>target)  return;if(sum == target){ret.push_back(path);return;}for(int i = pos;i<candidates.size();i++){path.push_back(candidates[i]);dfs(candidates,sum+candidates[i],i);path.pop_back();}}
};

 解法二：

class Solution {vector<vector<int>> ret;vector<int> path;int target;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int>& candidates,int sum, int pos){if(sum == target){ret.push_back(path);return;}if(sum>target || pos == candidates.size())  return;for(int k = 0;k*candidates[pos]+sum<=target;k++){if(k)   path.push_back(candidates[pos]);dfs(candidates,sum+k*candidates[pos],pos+1);}for(int k = 1;k*candidates[pos]+sum<=target;k++){path.pop_back();}}
};

三  矩阵搜索问题

3.1  N皇后 

51. N 皇后 - 力扣（LeetCode）

 

class Solution {bool checkCol[10], checkDig1[20], checkDig2[20];vector<vector<string>> ret;vector<string> path;
public:vector<vector<string>> solveNQueens(int n) {path.resize(n);for(int i = 0;i<n;i++)path[i].append(n,'.');dfs(n,0);return ret;}void dfs(int n, int row){if(row == n){ret.push_back(path);return;}for(int col = 0;col<n;col++){if(!checkCol[col]&&!checkDig1[row-col+n]&&!checkDig2[row+col]){path[row][col] = 'Q';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = true;dfs(n,row+1);path[row][col] = '.';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = false;}}}
};

3.2  有效的数独

36. 有效的数独 - 力扣（LeetCode）

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num])return false;row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}return true;}
};

3.3  解数独 

37. 解数独 - 力扣（LeetCode）

 

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:void solveSudoku(vector<vector<char>>& board) {for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j] == '.'){for(int num = 1; num<=9; num++){if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num]){board[i][j] = num + '0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board) == true)  return true;  //判断当前所填的数是否有效board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;  //无法填数时，则说明之前的填的数错误，返回错误}}}return true;}
};

3.4  单词搜素

79. 单词搜索 - 力扣（LeetCode）

 

class Solution {bool vis[7][7];int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;
public:bool exist(vector<vector<char>>& board, string word) {m = board.size(),n = board[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board,word,i,j,1))   return true;vis[i][j] = false;}}}return false;}bool dfs(vector<vector<char>>& board, string word,int i,int j,int pos){if(pos == word.size())  return true;for(int k = 0;k<4;k++){int x = i + dx[k],y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,word,x,y,pos+1))   return true;vis[x][y] = false;}}return false;}
};

3.5  黄金矿工

1219. 黄金矿工 - 力扣（LeetCode）

 本题的算法原理和单词搜索同，只不过多了一两个变量

class Solution {bool vis[16][16];int dx [4] = {0,0,1,-1};int dy [4] = {1,-1,0,0};int m,n,path,ret;
public:int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] != 0){vis[i][j] = true;dfs(grid,i,j,grid[i][j]);vis[i][j] = false;}}}return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int path){ret = max(ret,path);for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != 0){vis[x][y] = true;dfs(grid,x,y,path+grid[x][y]);vis[x][y] = false;}}}
};

3.6  不同路径III

980. 不同路径 III - 力扣（LeetCode）

 

class Solution {bool vis[21][21];int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n,step;int ret;
public:int uniquePathsIII(vector<vector<int>>& grid) {int bx,by;m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0; j < n;j++){if(grid[i][j] == 0)     step++;else if(grid[i][j] == 1){bx = i;by = j;}}}step += 2;vis[bx][by] = true;dfs(grid,bx,by,1);return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int count){if(grid[i][j] == 2){if(count == step) //判断是否合法ret++;return;}for(int k = 0;k < 4;k++){int x = i + dx[k],y = j + dy[k];if(x >=0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1){vis[x][y] = true;dfs(grid,x,y,count + 1);vis[x][y] = false;}}}
};

---

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解DFS，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！