论坛 › 分布式数据库 › dfs刷题排列问题 + 子集问题 + 组和问题总结

tsx81428 发表于 2025-3-22 07:44:38

dfs刷题排列问题 + 子集问题 + 组和问题总结

一、排列问题

全排列II

题目链接
https://i-blog.csdnimg.cn/direct/a822dbe62d3f437c880a130647327c95.png
题解

1. 这题和全排列那题框架是一样的，就是剪枝操纵不一样
2. 同一节点出现相同元素肯定会重复，所以把同一节点的相同元素剪掉
3. 同一个数只能出现一次，用check数组剪枝
分为两种环境举行剪枝：
1、只关心不正当的分支：
不正当的举行跳过（剪枝）
check == true || ( i != 0 &&nums == nums && check == false)
这个点是已经使用过的，或者是这个点和前一个点是相同的并且前一个点没有使用过，i != 0保证不越界
2、只关心正当的分支：
正当的分支才举行dfs
check == false && (i == 0 || nums != nums || check == true)
这个点没有被使用过并且该点为第一个点肯定可以举行dfs，或者是该点和前一个点不相同也可以dfs，或者是该点和前一个点相同，但是前一个点上一层已经使用过了，这个点这层可以继续使用，因为它们是用的不同位置

https://i-blog.csdnimg.cn/direct/501645b3691b455ea668a13721f194ab.png
代码

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check;
    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++)
      {
            // 合法的剪枝,不合法就不进行dfs
            // if((check == false)&&
            // (i == 0||nums != nums||check == true))
            // {
            //   check = true;
            //   path.push_back(nums);
            //   dfs(nums);
            //   // 恢复现场
            //   check = false;
            //   path.pop_back();
            // }

            // 考虑不合法的剪枝,跳过不合法的剪枝
            if((check == true)||
            (i != 0&&nums == nums&&check == false))
            continue;
      
                check = true;
                path.push_back(nums);
                dfs(nums);
                // 恢复现场
                check = false;
                path.pop_back();
      }
    }
};
优美的排列

题目链接
https://i-blog.csdnimg.cn/direct/650c495716b04111a75cf537514aaf36.png
题解

1. 画出决策树
2. 全局变量的设计：ret用来记载优美排列的个数，check数组检查是否可以剪枝，n设计成全局变量就不必要举行传参了
3. 剪枝：第一种剪枝不能出现重复的数，第二种剪枝不满意整除条件的
4. 回溯：如图我们每个位置都要举行判断，每个位置都会走一遍，递归完后举行恢复现场，把最后一位pop_back
5. 递归出口：当path路径的长度即是n时为递归出口
6. for循环的i = 1开始是因为要遍历所有的路径，dfs中pos+1是因为此位置遍历完会来到下一个位置举行遍历，画出决策树就很清晰了
https://i-blog.csdnimg.cn/direct/211666a0aad54fab8ccbad8c4ce1d98c.png
代码

class Solution
{
public:
    int n;
    int ret;
    bool check;
    vector<int> path;
    int countArrangement(int _n)
    {
      n = _n;
      dfs(1);
      return ret;
    }

    void dfs(int pos)
    {
      if(path.size() == n)
      {
            ret++;
            return;
      }

      for(int i = 1;i <= n;i++)
      {
            if(pos % i == 0 || i % pos == 0)
            {
                if(check == false)
                {
                  check = true;
                  path.push_back(i);
                  dfs(pos+1);
                  // 恢复现场
                  path.pop_back();
                  check = false;
                }
            }
      }
    }
};
二、子集问题

字母大小写全排列

题目链接
https://i-blog.csdnimg.cn/direct/ef1a9f04066748f2af61e8d376129de9.png
题解

1. 画出决策树
2. 全局变量：ret记载最终的结果，path记载每次的路径
3. 剪枝：没有剪枝
4. 回溯：到达叶子节点的时间记载完举行回溯，pop_back最后一个位置的数来到上一层
5. 递归出口：pos位置为n时，是最后一个数据的下一个位置，为递归出口
6. 这题和选和不选根本上是一样的，子集问题，pos这个位置变或者不变然后来到下一个位置，所以dfs(pos+1)，变的环境为小写字母时转为大写字母，大写转为小写，不变就直接push
https://i-blog.csdnimg.cn/direct/6ad716f4bf2340799c462323f19819ad.png
代码

class Solution
{
public:
    vector<string> ret;
    string path;
    vector<string> letterCasePermutation(string s)
    {
      dfs(s,0);
      return ret;
    }

    void dfs(string s,int pos)
    {
      // 为什么不能写pos == s.size()
      if(pos == s.size())
      {
            ret.push_back(path);
            return;
      }
      
      char ch = s;
      // 不变
      path.push_back(ch);
      dfs(s,pos+1);
      path.pop_back();

      // 变
      if(ch < '0' || ch > '9')
      {
            ch = change(ch);
            path.push_back(ch);
            dfs(s,pos+1);
            path.pop_back();
      }
    }
    char change(char ch)
    {
      if(ch >= 'a' && ch <= 'z') ch -= 32;
      else ch += 32;
      return ch;
    }
};
找出所有子集的异或总和再求和

题目链接
https://i-blog.csdnimg.cn/direct/54be7b86998f404b900d31c2dbbde690.png
题解

1. 画出决策树
2. 全局变量：用sum记载最终的结果，用path记载一个聚集的异或和
3. 剪枝：没有剪枝
4. 回溯：每次异或当前元素就抵消掉这个元素了，然后回到上一层
5. 递归出口：没有递归出口，每次把path加到sum中即可
6. for循环中每次从pos位置开始向后罗列，制止重复，dfs(i+1)，i+1就是数组中下一个位置的数，相当于剪枝了
https://i-blog.csdnimg.cn/direct/7cf0aa6ddd4b4d238706d29928c70c9b.png
代码

class Solution
{
public:
    long long sum = 0;// 记录全部路径的异或和
    long long path = 0;// 记录一条路径的异或和
    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;
            dfs(nums,i+1);
            path ^= nums;
            // 不能使用pos代替i,如果进行回溯回来,
            // 进行循环,path始终异或nums
      }
    }
};
三、组合问题

电话号码的字母组合

题目链接
https://i-blog.csdnimg.cn/direct/1b1ac53e2f43404fa2467afb12605c83.png
题解

1. 画出决策树
2. 全局变量：ret记载最终的结果，path记载每次的路径，哈希表记载下标的映射关系
3. 剪枝：没有剪枝
4. 回溯：到达叶子节点时，pop_back最后一个元素，恢复现场
5. 递归出口：path的长度和给定的数组的长度相同
6. for循环把所有的数都罗列出来了，所以i下标从0开始，dfs(pos+1)，每个位置罗列完跳到下一个位置继续罗列，这题主要是创建一个hash表记载每次的电话号码的数字对应的映射字符串
https://i-blog.csdnimg.cn/direct/b7842c57f8e746a4bd9c3db29d6cdfdb.png
代码

class Solution
{
public:
    vector<string> ret;
    string path;
    string hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    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(int i = 0;i < hash - '0'].size();i++)
      {
            path.push_back(hash - '0']);
            dfs(digits,pos+1);
            // 恢复现场
            path.pop_back();
      }
    }
};
括号天生

题目链接
https://i-blog.csdnimg.cn/direct/6427e97ccd9e4782ac0df6b04a771b16.png
题解

1. 画出决策树
2. 全局变量：path记载每次的路径，ret记载最终的结果，left记载左括号的数目，right记载右括号的数目
3. 剪枝：第一种右括号的数目大于即是左括号的数目，第二中左括号的数目大于即是n的数目，开始的时间只能给左扩号，右括号剪枝，左右括号相等时，不能参加右括号，左括号大于n不符合结果，即是n时，再往下加就大于n，必要剪枝
4. 回溯：如果是左括号回溯，pop_back最后一个元素，left–，如果是右括号回溯，pop_back最后一个元素，right–
5. 递归出口：右括号的数目即是n时，为左右括号相等的最终结果
https://i-blog.csdnimg.cn/direct/47a0e46f5df74f169ff1ac752f0cfd02.png
代码

class Solution
{
public:
    vector<string> ret;
    string path;
    int left,right;
    vector<string> generateParenthesis(int n)
    {
      dfs(n);
      return ret;
    }
   
    void dfs(int n)
    {
      if(right == n)
      {
            ret.push_back(path);
            return ;
      }

      if(left < n)
      {
            path.push_back('(');
            left++;
            dfs(n);
            path.pop_back();
            left--;
      }
      if(left > right)
      {
            path.push_back(')');
            right++;
            dfs(n);
            path.pop_back();
            right--;
      }

    }
};
组合

题目链接
https://i-blog.csdnimg.cn/direct/d8eed4f5483f45668297f9c2c10aa940.png
题解

1. 画出决策树
2. 全局变量：path记载每次的路径，ret记载最终的结果，k变为全局变量，不必要多传一个参数
3. 剪枝：不能重复出现相同的数剪枝，长度不够k也剪枝，这题可以从pos位置开始向后罗列，dfs(i+1)，i+1表示每次罗列当前数的下一个位置的数，相当于举行了剪枝
4. 回溯：到达叶子节点后，每次pop_back最后一个数
5. 递归出口：path的长度即是k的大小
https://i-blog.csdnimg.cn/direct/09cd7b6ec1d74ec29370f7ae233202aa.png
代码

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int k;
    vector<vector<int>> combine(int n, int _k)
    {
      k = _k;
      dfs(n,1);
      return ret;
    }

    void dfs(int n,int pos)
    {
      if(path.size() == k)
      {
            ret.push_back(path);
            return ;
      }

      for(int i = pos;i <= n;i++)
      {
            path.push_back(i);
            dfs(n,i+1);
            path.pop_back();// 恢复现场
      }
    }
};
目的和

题目链接
https://i-blog.csdnimg.cn/direct/dbd4dadd596c45119138cc956135d7ba.png
题解

1. 画出决策树
2. 全局变量：ret记载最终的结果，target变为全局变量就少传一个参数
3. 剪枝：没有剪枝
4. 回溯：函数自动回溯，将path作为参数，记载每条路径的大小，回到上一层，path变为了没有加减之前的path
5. 递归出口：最终的path即是target的大小，ret++
6. 这题就是每个数两种环境，要么加，要么减
https://i-blog.csdnimg.cn/direct/e110e62797764054a9b06c2b7efdba50.png
代码

class Solution
{
public:
    int ret,target;
    int findTargetSumWays(vector<int>& nums, int _target)
    {
      target = _target;
      dfs(nums,0,0);
      return ret;
    }

    void dfs(vector<int>& nums,int pos,int path)
    {
      if(pos == nums.size())
      {
            if(target == path)
            ret++;
            return;
      }

      // 加法,放在参数中函数帮我们自动恢复现场了
      dfs(nums,pos+1,path + nums);

      // 减法
      dfs(nums,pos+1, path - nums);
    }
};
组合总和

题目链接
https://i-blog.csdnimg.cn/direct/1fbbb6587b7542339fd968f3d7732f30.png
题解

解法一：每个pos位置填
1. 画出决策树
2. 全局变量：ret记载最终的结果，path记载每条路径，target变为全局变量就不必要传参target了
3. 剪枝：如果这条路径的和大于target剪枝，如果选择的路径重复了剪枝，这种可以使用i = pos位置开始向后罗列，dfs(i)，i表示每次从当前这个数向后罗列，不必要重复罗列这个数前面的数，就制止了重复的路径，到达了剪枝的效果
4. 回溯：sum在函数的参数中自动举行了回溯，pop_back最后一个元素，回到上一层
5. 递归出口：目的值即是记载的路径总和就找到一条路径，参加ret中，并返回给上一层
https://i-blog.csdnimg.cn/direct/debfdea6551d43ab8aef72a041efd68f.png
代码

class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int target;
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
      target = _target;
      dfs(candidates,0,0);
      return ret;
    }

    void dfs(vector<int> candidates,int pos,int sum)
    {
      if(sum == target)
      {
            ret.push_back(path);
            return;
      }
      // 枚举完了所有的位置也不是target,这个总和比较小
      if(pos == candidates.size()) return;

      for(int i = pos;i < candidates.size();i++)
      {
            if(sum > target) continue;
            
            path.push_back(candidates);
            dfs(candidates,i,sum + candidates);
            path.pop_back();
      }
    }
};
解法二：罗列每个数的数目
1. 和解法一不一样的地方就是dfs函数的实现不一样

https://i-blog.csdnimg.cn/direct/d345c635f5374f51a183a4f223da5443.png
class Solution
{
public:
    vector<vector<int>> ret;
    vector<int> path;
    int target;
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
      target = _target;
      dfs(candidates,0,0);
      return ret;
    }

    void dfs(vector<int> candidates,int pos,int sum)
    {
      if(sum == target)
      {
            ret.push_back(path);
            return;
      }
      // 枚举完了所有的位置也不是target,这个总和比较小
      if(pos == candidates.size() || sum > target) return;
         
      // 枚举个数
      for(int k = 0;sum + k * candidates <= target;k++)
      {
            if(k) path.push_back(candidates);
            dfs(candidates,pos+1,sum + k*candidates);
      }
      
      // 整块恢复现场
      for(int k = 1;sum + k * candidates <= target;k++)
      {
            path.pop_back();
      }
    }
};
总结

1. 最重要的就是画出决策树
2. 全局变量：一般是path记载路径，ret记载各个路径的结果
3. 剪枝：看题目分析和看决策树
4. 回溯：一般是pop_back最后一个元素
5. 递归出口：看题目条件，或者是叶子节点
https://i-blog.csdnimg.cn/direct/585c787bafda4123b25b8d0b592b7a86.png

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: dfs刷题排列问题 + 子集问题 + 组和问题总结