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

一篇带你完全掌握DFS

Chris-zz

1829人浏览 · 2024-09-17 14:09:50

Chris-zz · 2024-09-17 14:09:50 发布

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

文章目录

前言

本篇详细介绍了进一步介绍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，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！

松山湖开发者村综合服务平台

助力广东及东莞地区开发者，代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展，成为松山湖开发者首选的工作与学习平台

更多推荐

深入浅出Python——Python基础语法全解

前言：Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。文章目录一、Python简介1. 了解Python2. Python介绍3. Python特点4. Python发展历史5. Python版本二、Python解释器1. 解释器的作用2. 解释器的安装三、PyCharm安装与使用1. PyCharm的作用2. PyCharm安装与使用四、注释1. 注释的作用2. 注