dfs专题四：综合练习

key：画出决策树（就是找个简单例子模拟一下的树状决策图）

dfs传参 or 全局变量：

• int, double等常量/比较小的变量，可以dfs参数传递
• vector等线性O（N）变量，要用全局变量 + 回溯， 降低时间&空间复杂度

dfs主要用途：

• 全排列
• 求子集
• 路径枚举

1.找出所有子集的异或综合再求和

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

就是求子集

code

class Solution {
public:int ret = 0;int cur = 0;int subsetXORSum(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int idx)//对idx下标选择取舍{// 出口if(idx >= nums.size()){printf("ret = %d\n", ret);ret += cur;return;}// 主题//    不要dfs(nums, idx + 1);//    要cur ^= nums[idx];dfs(nums, idx + 1);cur ^= nums[idx]; // 回溯}
};

2.全排列II

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

不重复全排列

code

class Solution {
public:vector<vector<int>> ans;vector<int> cur;vector<bool> used;vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());used = vector<bool>(nums.size(), false);dfs(nums, 0);return ans;}void dfs(vector<int>& nums, int idx)// 选择第idx下标元素{// 出口if(idx >= nums.size()) {ans.push_back(cur);return;}// 主体for(int i = 0; i < nums.size(); i++){if(!used[i] && (i == 0 || !used[i-1] || nums[i] != nums[i-1])){cur.push_back(nums[i]);used[i] = true;dfs(nums, idx + 1);used[i] = false;cur.pop_back(); // 回溯}}}
};

3.电话号码的字母组合

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

组合

code

class Solution {
public:vector<string> ans;string cur; // 全局变量unordered_map<char, string> map = {{'2', "abc"}, {'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"}, {'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};vector<string> letterCombinations(string digits) {if(!digits.size()) return {};dfs(digits, 0);return ans;}void dfs(string& digits, int idx){// 出口if(idx >= digits.size()){ans.push_back(cur);return;}for(char ch:map[digits[idx]]){cur += ch;dfs(digits, idx + 1);cur.pop_back();// 回溯}}
};

4.括号生成

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

有条件全排列

code

class Solution {
public:vector<string> ans = {};string path = "";// 全局变量int sum = 0;// 全局变量int n;vector<string> generateParenthesis(int _n) {// key: '(' = 1, ')' = -1, 令sum属于[0, 3]即可n = _n;dfs(0);return ans;}void dfs(int idx){// 出口if(sum < 0 || sum > n) return;// 剪枝if(idx >= 2 * n){if(sum != 0) return;ans.push_back(path);return;}// 主体//  (path += '(';sum += 1;dfs(idx + 1);sum -= 1; // 回溯path.pop_back();//  )path += ')';sum += -1;dfs(idx + 1);sum -= -1;path.pop_back();    // 回溯}
};

5.组合

link:77. 组合 - 力扣（LeetCode）

组合

code

class Solution {
public:int n, k;vector<vector<int>> ans;vector<int> path;vector<bool> used;vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;used = vector<bool>(n, false);dfs();return ans;}void dfs(){// 出口if(path.size() >= k) {ans.push_back(path);return;}// 主体for(int i = 1; i <= n; i++){if(used[i] ) return;// 剪枝 不用continue 保证path有序（倒序path.push_back(i);used[i] = true;dfs();used[i] = false;path.pop_back();    // 回溯}}
};

6.目标和

link:494. 目标和 - 力扣（LeetCode）

满足条件的子集

暴力枚举

code

class Solution {
public:int ans = 0;int path = 0;vector<int> nums;int target;int findTargetSumWays(vector<int>& _nums, int _target) {nums = _nums;target = _target;// 类似子集问题， key为每个元素取舍（+/-)dfs(0);return ans;}void dfs(int idx){// 出口if(idx >= nums.size()){if(path == target) ans++;return;}// body//  +path += nums[idx];dfs(idx + 1);path -= nums[idx];//  -path += -nums[idx];dfs(idx + 1);path -= -nums[idx];}
};

7.组合总数

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

code

class Solution {
public:vector<vector<int>> ans;vector<int> path;int sum = 0;int target;vector<int> candidates;vector<vector<int>> combinationSum(vector<int>& _candidates, int _target) {candidates = _candidates;target = _target;sort(candidates.begin(), candidates.end());dfs(0);return ans;}void dfs(int bgn)// 只能从[bgn:]中选择下一个， 保证path升序{// 出口if(sum >= target){if(sum == target) ans.push_back(path);return;//剪枝}// bodyfor(int i = bgn; i < candidates.size(); i++){sum += candidates[i];path.push_back(candidates[i]);dfs(i);path.pop_back();sum -= candidates[i];// 回溯}}
};

8.字母大小写全排列

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

code

class Solution {
public:vector<string> ans;string path;vector<string> letterCasePermutation(string _s) {path = _s;dfs(0);return ans;}void dfs(int idx){// 出口if(idx >= path.size()){ans.push_back(path);return;}// bodychar cp = path[idx];//  大小写转换if(isalpha(path[idx])){path[idx] = toupper(path[idx]);dfs(idx + 1);path[idx] = tolower(path[idx]);dfs(idx + 1);}else dfs(idx + 1);path[idx] = cp;// 回溯}
};

9.优美的排列

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

求满足条件的全排列的个数，及时剪枝即可

求满足条件的全排列 + 及时剪枝

code

class Solution {
public:int ans = 0;vector<bool> used;int countArrangement(int n) {// 虽然是dfs暴力枚举，但只要及时剪枝， 复杂度就并不高used = vector<bool>(n + 1, false);dfs(1, n);return ans;}void dfs(int idx, int n){// 出口if(idx > n){ans++;return;}// bodyfor(int i = 1; i <= n; i++){if(used[i] || (i % idx != 0 && idx % i != 0)) continue;//剪枝used[i] = true;dfs(idx + 1, n);used[i] = false;// 回溯}}
};

10.N皇后

link:51. N 皇后 - 力扣（LeetCode）

全排列 + 剪枝

code

class Solution {
public:vector<vector<string>> ans;vector<string> path;vector<bool> used;unordered_set<int> set1, set2;vector<vector<string>> solveNQueens(int n) {path = vector<string>(n, string(n, '.'));used = vector<bool>(n, false);dfs(0);return ans;}void dfs(int col){// 出口if(col >= path.size()){ans.push_back(path);return;}// bodyfor(int i = 0; i < path.size(); i++){if(used[i] || !check(col, i)) continue;// 剪枝set(col, i);path[col][i] = 'Q';dfs(col + 1);path[col][i] = '.';reset(col, i);// 回溯}}void set(int col, int row){used[row] = true;set1.insert(col+row);set2.insert(col-row);}void reset(int col, int row){used[row] = false;set1.erase(col+row);set2.erase(col-row);}bool check(int col, int row){return (!set1.count(col + row)) && (!set2.count(col - row));}
};

11.有效的数独

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

和dfs没什么关系， 就是模拟题， 为下题做铺垫

code

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {// rows检查for(vector<char> vc:board){if(repeat(vc)) return false;}// cols检查for(int col = 0; col < 9; col++){vector<char> tmp = {};for(int row = 0; row < 9; row++){tmp.push_back(board[row][col]);}if(repeat(tmp)) return false;}// 方块检查for(int row = 0; row < 9; row+=3)for(int col = 0; col < 9; col+=3){vector<char> tmp = {};for(int r = 0; r < 3; r++)for(int c = 0; c < 3; c++){tmp.push_back(board[row+r][col+c]);}if(repeat(tmp)) return false;}return true;}bool repeat(vector<char>& nums){vector<bool> used(10, false);for(char ch:nums){if(ch == '.') continue;if(used[ch-'0']) return true;used[ch-'0'] = true;}return false;}
};

12.解数独

Link:37. 解数独 - 力扣（LeetCode）

全排列 + 剪枝

code

class Solution {
public:vector<vector<char>> board;bool row[9][10];bool col[9][10];bool grid[3][3][10];void set(int r, int c, int num){row[r][num] = true;col[c][num] = true;grid[r / 3][c / 3][num] = true;}void reset(int r, int c, int num){row[r][num] = false;col[c][num] = false;grid[r / 3][c / 3][num] = false;}bool check(int r, int c, int num){return (!row[r][num]) && (!col[c][num]) && (!grid[r / 3][c / 3][num]);}void solveSudoku(vector<vector<char>>& _board) {memset(row, false, sizeof row);memset(col, false, sizeof col);memset(grid, false, sizeof grid);// 录入已有信息board = _board;for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++){if(board[i][j] == '.') continue;set(i, j, board[i][j] - '0');}if(!dfs()) printf("error!! 未找到\n");_board = board;}bool dfs(){for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++){if(board[i][j] != '.') continue;for(int num = 1; num <= 9; num++){if(check(i, j, num))// 剪枝{set(i, j, num);board[i][j] = num + '0';if(dfs()) return true;// 及时返回board[i][j] = '.';reset(i, j, num);// 回溯}}return false;// 剪枝}return true;}};

13.单词搜索

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

dfs枚举 + 剪枝

注意dfs(i, j, idx)作用：再board[i][j]旁边找word[idx]

每次使用dfs前后都要set/reset

code

class Solution {
public:vector<vector<char>> board; string word;vector<vector<bool>> used;vector<pair<int, int>> add = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};bool exist(vector<vector<char>>& _board, string _word) {board = _board;word = _word;used = vector<vector<bool>> (board.size(), vector<bool>(board[0].size(), false));for(int i = 0; i <board.size(); i++){for(int j = 0; j < board[0].size(); j++){if(board[i][j] != word[0]) continue;used[i][j] = true;if(dfs(i, j, 1)) return true;used[i][j] = false;}}return false;}bool dfs(int row, int col, int idx){// 出口if(idx == word.size()) return true;// bodyfor(auto[addx, addy] : add){auto[x, y] =make_pair(row + addx, col + addy);if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || used[x][y] || board[x][y] != word[idx]) continue;used[x][y] = true;if(dfs(x, y, idx + 1)) return true;// 及时上传trueused[x][y] = false;// 回溯}return false;}
};

14.黄金矿工

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

dfs枚举

code

class Solution {
public:int ans = 0;int path = 0;int getMaximumGold(vector<vector<int>>& grid) {for(int i = 0; i < grid.size(); i++)for(int j = 0; j < grid[0].size(); j++){if(grid[i][j] == 0) continue;int cp = grid[i][j];path += cp;grid[i][j] = 0;dfs(i, j, grid);grid[i][j] = cp;path -= cp;}return ans;}vector<int> dx = {0, 0, 1, -1};vector<int> dy = {1, -1, 0, 0};void dfs(int row, int col, vector<vector<int>>& grid){  ans = max(ans, path);// 每次更新// bodyfor(int i = 0; i < 4; i++){int x = row + dx[i], y = col + dy[i];if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() ||grid[x][y] == 0) continue;// 及时判断int cp = grid[x][y];grid[x][y] = 0;path += cp;dfs(x, y, grid);path -= cp;grid[x][y] = cp;    // 回溯}}
};

15.不同路径III

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

dfs枚举

code

class Solution {
public:int ans = 0;int path = 0;// 已经走过的格子数int m, n;int cnt = 0;// -1个数vector<vector<bool>> used;int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();used = vector<vector<bool>>(m, vector<bool>(n, false));int x = 0, y = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){cnt += (grid[i][j] == -1);if(grid[i][j] == 1){x = i;y = j;}}used[x][y] = true;path += 1;dfs(x, y, grid);path -= 1;used[x][y] = false;return ans;}vector<int> dx = {0, 0, 1, -1};vector<int> dy = {1, -1, 0, 0};void dfs(int row, int col, vector<vector<int>>& grid){// 出口if(grid[row][col] == 2){if(path == m * n - cnt) ans++;return;}// bodyfor(int i = 0; i < 4; i++){int x = row + dx[i], y = col + dy[i];if(x < 0 || x >= m || y < 0 || y >= n || used[x][y] || grid[x][y] == -1) continue;// 剪枝used[x][y] = true;path += 1;dfs(x, y, grid);path -= 1;used[x][y] = false;// 回溯}}
};