???學習的道路很枯燥，希望我們能并肩走下來!

目錄

文章目錄

前言

一??排列、子集問題

1.1??全排列I

1.2? 子集I?

?1.3? 找出所有子集的異或總和

1.4? 全排列II

1.5? 字母大小寫全排列

1.6? 優(yōu)美的排列

二? 組合問題?

2.1? 電話號碼的數(shù)字組合

?2.2? 括號生成

2.3? 組合?

2.4? 目標和

2.5? 組合總和

三? 矩陣搜索問題

3.1? N皇后?

3.2? 有效的數(shù)獨

3.3? 解數(shù)獨?

3.4? 單詞搜素

3.5? 黃金礦工

3.6? 不同路徑III

總結

---

前言

本篇詳細介紹了進一步介紹DFS，讓使用者對DFS有更加深刻的認知，而不是僅僅停留在表面，更好的模擬，為了更好的使用. 文章可能出現(xiàn)錯誤，如有請在評論區(qū)指正，讓我們一起交流，共同進步！

---

我們在做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);//回溯-> 恢復現(xiàn)場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? 優(yōu)美的排列

526. 優(yōu)美的排列 - 力扣（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? 電話號碼的數(shù)字組合

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; //記錄有效括號的對數(shù)
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? 有效的數(shù)獨

36. 有效的數(shù)獨 - 力扣（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? 解數(shù)獨?

37. 解數(shù)獨 - 力扣（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;  //判斷當前所填的數(shù)是否有效board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;  //無法填數(shù)時，則說明之前的填的數(shù)錯誤，返回錯誤}}}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，如果對你有幫助給個👍贊鼓勵一下吧！！
🎉🎉🎉世上沒有絕望的處境，只有對處境絕望的人。
感謝每一位一起走到這的伙伴，我們可以一起交流進步！！！一起加油吧！！