LeetCode刷题 DFS+回溯

阅读原文时间：2023年07月08日阅读：1

一、DFS介绍
二、LeetCode 实战

一、DFS介绍

DFS（Depth-First-Search）： 深度优先遍历（DFS） 和 广度优先遍历（BFS） 是图论中两种非常重要，也是非常常见的两种算法思想，我们这里只介绍深度优先遍历。深度优先遍历 是在连通图中从某一个未被访问的节点V开始，按照一个方向走下去，直到走到尽头，然后再返回到上一个节点，先递归到底，然后再回溯是DFS的一大特点。

对于DFS的应用，我们要注意：

DFS不一定需要递归；
在使用DFS时，一些必要的剪枝操作可以节省大量的时间；
在使用递归来实现DFS时，一定要明确该递归函数的返回值的定义；

二、LeetCode 实战

题目链接

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

提示：

0 <= digits.length <= 4

digits[i] 是范围 ['2', '9'] 的一个数字。

解法思路

本题很好的解释了DFS并不是一定需要递归，当然本题的非递归解法也没有采用DFS的思想，只是说有很多种途径，从思想上来说，本题的非递归解法是对BFS的一种应用

本题的解题思想就是枚举所有的可能，即当我们读取到一个字符，就将他所有可能出现的结果枚举出来，并放到一个dp数组中，然后我们每次枚举完所有的结果，就将dp数组的结果赋值给res，然后最终我们返回res数组就可以

解题步骤

循环遍历给出digits中的每一个字符
枚举当前字符与res数组的所有组合情况，并将结果存储在do数组中
将dp数组赋值给res，并将dp数组置空
继续循环，到结束，然后返回res

代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return vector<string>();
        vector<string> letter{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> dp,res;
        res.push_back("");
        int len=digits.size();
        for(int i=0;i<len;++i)
        {
            string t=letter[digits[i]-'2'];
            for(int j=0;j<t.size();j++)
                for(int k=0;k<res.size();++k)
                    dp.push_back(res[k]+t[j]);
            res=dp;
            dp.clear();
        }
        return res;
    }
};

题目链接

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

提示：

m == board.length

n = board[i].length

1 <= m, n <= 6

1 <= word.length <= 15

board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路

典型的路径搜索问题，我们需要枚举所有起点开始的位置，直到枚举完全部，或者是枚举到正确路径的起点位置。我们进行DFS时，先判断当前位置字符是否匹配，if true 我们就向上下左右继续做递归；if false 我们就返回上一层

解题步骤

枚举所有起点位置，如果起点位置匹配，我们就进行DFS，否则枚举下一个起点位置
进入dfs，先判断所给的参数是否在board内，如果不在return false；且l是否达到word的长度，如果达到return true；
然后向上下左右依次做dfs递归

代码

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

题目链接

给定一个没有重复数字的序列，返回其所有可能的全排列。

本题其实就是一个排序组合的问题，由于没有重复的数字，所以我们不用考虑相同数字的相对位置导致的排列重复问题。而一般而言，这种排列问题，我们只有两种思路：1.每个位置上应该放哪个数字；2.每个数字应该放到哪个位置上。这两种思路，其实是给我们提供了两种解题思路，解法一按照第一种思路讲解，解法二按照第二种思路讲解

解题思路一

1.每个位置上应该放哪个数

这种思想实际上是最容易考虑的，想想我们在数学学习排列组合时，利用画图的方法求解排列问题时，首先会将第一个位置的所有可能列出来，然后再列出第二个位置的所有可能，然后是第三个，… …，直到最后一个。这就是我们第一种思想，我们的具体实现方法是先在第一个位置上进行循环遍历所有的可能，并且递归到第二个位置；然后循环遍历第二个位置的所有可能，并且递归到第三个位置，这样一直做下去。注意由于我们是求排列总和，并且排列是不能重复使用某一个数字的，所以在我们上一层递归到下一层的时候，要记得将当前数字的可用性记为不可用。

比如，给出数组[1,2,3]，我们在求这一个的所有排列组合的时候，首先我们开辟一个长为 3 的数组[null,null,null]，然后考虑第一个位置的情况[1,n,n]、[2,n,n]、[3,n,n]，我们在循环遍历这三种情况的时候，考虑第一种情况[1,n,n]递归下去为[1,2,n]、[1,3,n]，然后再按每种情况继续递归

解题步骤

构建位置
在每一个位置上遍历所有可能
当遍历到最后一个位置时，将path添加到ans中
返回ans

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> sk;
    int n;
    vector<vector<int>> permute(vector<int>& nums) {
        n=nums.size();
        path=vector<int>(n);
        sk=vector<bool>(n);
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int>& nums,int cnt)
    {
        if(cnt==n)
        {
            ans.push_back(path);
            return;
        }
        for(int i=0;i<n;++i)
        {
            if(!sk[i])
            {
                sk[i]=true;
                path[cnt]=nums[i];
                dfs(nums,cnt+1);
                sk[i]=false;
            }
        }
        return;
    }
};

解法思路二

2.每个数字应该放到哪个位置

这个想法在高中数学中，考虑排位置、站队方式等等一系列问题时用的比较多，该思想的主要想法是我们先让某一个数字去选位置，那么当这个数字选完之后，第二个数字只能从剩余的位置中进行选择，当所有的数字都选择完毕，我们就会得到一种排列组合

所以这里我们进行的解题思路会与解法一略有不同，我们在最外层遍历数字，进入递归之后我们便进行遍历位置

解题步骤

创建位置
遍历数字，然后让数字将位置遍历
当所有的数字遍历完成，将path添加到ans中
返回ans

代码

class Solution {
public:
    int n;
    vector<bool> st;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permute(vector<int>& nums) {
        n=nums.size();
        st=vector<bool>(n);
        path=vector<int>(n);
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int>& nums,int u)
    {
        if(u==n)
        {
            ans.push_back(path);
            return;
        }
        for(int i=0;i<n;++i)
        {
            if(!st[i])
            {
                st[i]=true;
                path[i]=nums[u];
                dfs(nums,u+1);
                st[i]=false;
            }
        }
    }
};

题目链接

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

本题与上一题相差不大，只不过多了重复元素，这是我们可以做一下处理，我们将相同的元素进行人为的排序即我们给相同元素打上标签，让其按照一定的顺序进行排列，那样我们就不用来考虑[1(1),1(2)]与[1(2),1(1)]的重复排序

由于两题相差不大，同时也都有两种解法，这里只写出一种，另一种自己思考，主要考虑如何给重复元素排序

解法思路

解题步骤

sort给定的数组
我们进行遍历递归，并且规定后一个相同元素只能排列在前一个相同元素之后
递归到终点将path添加到ans
递归完成return ans

代码

class Solution {
public:
    int n;
    vector<bool> st;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n=nums.size();
        st=vector<bool>(n);
        path=vector<int>(n);
        sort(nums.begin(),nums.end());
        dfs(nums,0,0);
        return ans;
    }
    void dfs(vector<int>& nums,int u,int start)
    {
        if(u==n)
        {
            ans.push_back(path);
            return;
        }
        for(int i=start;i<n;++i)
        {
            if(!st[i])
            {
                st[i]=true;
                path[i]=nums[u];
                dfs(nums,u+1,(u+1<n && nums[u+1]==nums[u])?i+1:0);
                st[i]=false;
            }
        }
    }
};

题目链接

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

解法思路一

组合数其实是不纠结数字之间相对顺序的，类似于集合，所以我们考虑的是哪个数字应该放进去，这样一来，我们只需要对排列的解法将重复的排列去掉即可

代码

class Solution {
public:
    int n;
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> subsets(vector<int>& nums) {
        n=nums.size();
        st=vector<bool>(n);
        for(int i=0;i<=n;++i)
            dfs(nums,i,0,0);
        return ans;
    }
    void dfs(vector<int>& nums,int cnt,int u,int start)
    {
        if(u==cnt)
        {
            ans.push_back(path);
            return;
        }
        for(int i=start;i<n;++i)
        {
            if(!st[i])
            {
                st[i]=true;
                path.push_back(nums[i]);
                dfs(nums,cnt,u+1,i+1);
                path.pop_back();
                st[i]=false;
            }
        }
    }
};

解法思路二

组合，就是选那些数字，我们如果人为规定选中该数字记为1，不选中记为0，则利用二进制数可以很好的解决这个问题

代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        for(int i=0;i<1<<nums.size();++i)
        {
            vector<int> now;
            for(int j=0;j<nums.size();++j)
                if(i>>j & 1) now.push_back(nums[j]);
            res.push_back(now);
        }
        return res;
    }
};

题目链接

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

解题思路

对于上一题的子集由于我们没有重复的数字，所以可以有比较巧妙的解法，而对于有重复数字的子集，我们提供的就是一种通用的方法。我们这样想，将相同的数字先进行分组，比如[1,1,1]可分为[]、[1]、[1,1]、[1,1,1]这四种，然后，我们将所有的数字都这样进行处理，那么我们，只需要将这些不同数字的组合进行排列即可，这样就成了一个排列问题，但是实现起来可能，与正常的排列不同

代码

class Solution {
public:
    int n;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        n=nums.size();
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int>& nums,int cnt)
    {
        if(cnt==n)
        {
            ans.push_back(path);
            return;
        }
        int k=0;
        while(cnt+k<n && nums[cnt]==nums[cnt+k]) k++;
        for(int i=0;i<=k;++i)//这里用<=的原因是我们需要将空也算进去算一种，这样1个数字要循环两遍
        {
            dfs(nums,cnt+k);
            path.push_back(nums[cnt]);
        }
        for(int i=0;i<=k;++i) path.pop_back();
        return;
    }
};

题目链接

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。

解集不能包含重复的组合。

解题思路

枚举所有长度为 k 的数字组合，并判断和是否为 n 。如果是则添加到 ans；如果不是则继续枚举

解题步骤

枚举所有长度为 k 的数字组合，这点参照子集
判断和是否为n
返回ans

代码

class Solution {
public:
    int num[9]={1,2,3,4,5,6,7,8,9};
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> sk;
    vector<vector<int>> combinationSum3(int k, int n) {
        path=vector<int>(k);
        sk=vector<bool>(9);
        dfs(k,n,0);
        return ans;
    }
    void dfs(int k,int n,int start)
    {
        if(k==0)
        {
            if(n==0) ans.push_back(path);
            return;
        }
        for(int i=start;i<9;++i)
        {
            if(!sk[i])
            {
                sk[i]==true;
                path[k-1]=num[i];
                dfs(k-1,n-num[i],i+1);
                sk[i]=false;
            }
        }
        return;
    }
};

题目链接

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量

提示：

1 <= n <= 9

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

解题思路

本题我们采用枚举所有queen的所有位置来进行判断，如果符合题目给出的规则，我们就令ans++，否则我们就枚举下一个，这是这个题的基本思想

进一步，我们需要考虑，如何判定某一个位置上是可以放置queen的？我们可以考虑使用一个nxn的矩阵来进行存储，然而这样带来的一个问题是，我们在进行枚举位置时，更新这个矩阵的时间复杂度，将是O(n)的，并且在复原这个矩阵时，时间复杂度同样时O(n)。综上考虑，我们不建议采用这种方式。

那么我们应该如何考虑这个问题。我们使用了直线的方程这一个思想来进行问题的解决，我们的所有的址线都可以用x+y、x-y或者单独的x、y来进行表示，区别只是截距不同，那么我们利用下标表示截距，可构建相应的数组表示直线，而每次我们更新，所需要的时间复杂度只是O(1)，这样就比较方便

解题步骤

构建列、y-x、x+y数组，用来表示坐标为(x,y)的位置是否能用
我们逐行或者是说逐个queen进行递归
如果递归到最后一行，ans++；否则返回继续枚举其他位置
返回ans

代码

class Solution {
public:
    vector<bool> col;
    vector<bool> pd,qd;
    int ans=0;
    int _n;
    int totalNQueens(int n) {
        col=vector<bool>(n);
        pd=qd=vector<bool>(2*n);
        _n=n;
        dfs(0);
        return ans;
    }
    void dfs(int x)
    {
        if(x==_n)
        {
            ans++;
            return;
        }
        for(int y=0;y<_n;++y)
        {
            if(!col[y] && !pd[x+y] && !qd[y-x+_n])
            {
                col[y]=pd[x+y]=qd[y-x+_n]=true;
                dfs(x+1);
                col[y]=pd[x+y]=qd[y-x+_n]=false;
            }
        }
        return;
    }
};

题目链接

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

解题思路

本题与N-Queen II比较类似，同样是通过枚举进行解决。不过，我们这一次是枚举每一个未填入数字的空格可能填入的数字进行解决。我们同样面临一个问题如何保存每一个空格的数字可用性？

按照题目要求，每一行每一列每一个3x3区域中的19的数字只能出现一次，那么我们便需要3个量来进行保存，分别是row，col，st。当然我们再继续考虑这三个量。对于行row，有九行每一个都要保存19的数字可用性，所以我们需要一个二维矩阵，9x9；同理列col也是一样；而对于3x3的区域，我们为了便于后面进行编程，我们给其一个三维矩阵，3x3x9

准备好上述的东西，我们便可以进行编程了

代码

class Solution {
public:
    vector<vector<bool>> row,col;
    vector<vector<vector<bool>>> st;
    vector<vector<char>> ans;

    void solveSudoku(vector<vector<char>>& board) {
        row=col=vector<vector<bool>>(9,vector<bool>(9));
        st=vector<vector<vector<bool>>>(3,vector<vector<bool>>(3,vector<bool>(9)));
        for(int i=0;i<9;++i)
        {
            for(int j=0;j<9;++j)
            {
                char c=board[i][j];
                if(c!='.')
                {
                    row[i][c-'1']=col[c-'1'][j]=st[i/3][j/3][c-'1']=true;
                }
            }
        }
        dfs(board,0);
        board=ans;
        return;
    }

    void dfs(vector<vector<char>>& board,int n)
    {
        if(n==81)
        {
            ans=board;
            return;
        }
        int x=n/9,y=n%9;
        char c=board[x][y];
        if(c=='.')
        {
            for(int i=1;i<=9;++i)
            {
                if(!row[x][i-1] && !col[i-1][y] && !st[x/3][y/3][i-1])
                {
                    row[x][i-1]=col[i-1][y]=st[x/3][y/3][i-1]=true;
                    board[x][y]='0'+i;
                    dfs(board,n+1);
                    board[x][y]=c;
                    row[x][i-1]=col[i-1][y]=st[x/3][y/3][i-1]=false;
                }
            }
        }
        else dfs(board,n+1);
        return;
    }
};

题目链接

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

注意:

给定的火柴长度和在 0 到 10^9之间。

火柴数组的长度不超过15。

解题思路

此题可考虑成找到四个组合使得，这四个组合的和都等于正方形边长

其中正方形的边长为周长s/4，找寻组合，我们上面已经介绍了很多种方法，参考借用即可，这里我们需要注意，在进行找组合的时候，我们一定要，从大数子往小数字进行寻找，至于为什么，我们可以这样考虑，如果大数字和一个小数字能构成边长，却因为三个小数字组合一起而丢失，就会被判定不能构成正方形

我们这一题只给出代码，自行看代码

代码

class Solution {
public:

    vector<bool> st;

    bool makesquare(vector<int>& nums) {
        int sum = 0;
        for (auto num : nums) sum += num;
        if (!sum || sum % 4) return false;

        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());

        st = vector<bool>(nums.size());

        return dfs(nums, 0, 0, 0, sum / 4);
    }

    bool dfs(vector<int>& nums, int u, int cur, int start, int length)
    {
        if (u == 4) return true;
        if (cur == length) return dfs(nums, u + 1, 0, 0, length);

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i] && cur + nums[i] <= length)
            {
                st[i] = true;
                if (dfs(nums, u, cur + nums[i], i + 1, length)) return true;
                st[i] = false;

                while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i ++ ;
                if (!cur) return false;
                if (cur + nums[i] == length) return false;
            }

        return false;
    }
};

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

LeetCode 周赛上分之旅 #49 再探内向基环树

代码随想录算法训练营第二十九天| 491.递增子序列 46.全排列 47.全排列 II

C++算法之旅、05 基础篇 | 第二章数据结构

代码随想录算法训练营第二十八天| 93.复原IP地址 78.子集 90.子集II

代码随想录算法训练营Day42 动态规划

LeetCode 周赛上分之旅 #39 结合中心扩展的单调栈贪心问题