当前位置：首页 > article >正文

穷举vs暴搜vs深搜vs回溯vs剪枝_全排列_子集

article 2025/1/5 7:13:35

46. 全排列

递归解决：一开始选一个数，递归进入下一层再选一个新的数，直到到最后一个数。反会上一层遍历其它数。

每次递归到叶子节点就找到了一种组合，思路有了具体怎么实现？

1.怎么记录每条路径？
定义一个全局的path数组记录一条路径的数，再定义一个全局的二维数组re记录每条路径。

2.怎么判断是否到达叶子节点？
当path.size()==nums.size() 把路径path存入re中并直接返回

3.剪枝每一次都要取不同的数，怎么实现？

同样定义一个全局的数组check，用它记录数是否被使用过。该数在nums的下标映射在check中判断是否遍历过。

4.当我们从下层返回到上一层的函数时要进行回溯。

因为path check是全局的，我们要把path check进行还原。path去到最后一个数字，check把对应下标改为false。

5.递归出口

叶子节点直接返回。(不进行回溯，回到上层函数再回溯。因为不止叶子节点返回时要回溯)

class Solution {
    vector<vector<int>> re;
    vector<int> path;
    bool check[7];
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return re;
    }
    void dfs(vector<int>&nums)
    {
        if(path.size()==nums.size())
        {
            re.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;
            }
        }
    }
};

78. 子集

方法一：对于每一个数我们都有两种情况选和不选，把所有情况枚举出来就是结果。

这样我们就画出了一个二叉树，遍历该二叉树，叶子节点就是结果。

1.我们怎么知道该对哪个数进行选择呢？

给dfs函数传一个参数，用来标记该对那个数进行选择。

2.怎么进行选择？
定义全局path记录，选择就push_back()+递归不选择就直接递归

3.回溯

回到上一层时，恢复现场，path.pop

4.递归出口

当我们对最后一个数选择完时，就可以保存结果并返回

class Solution {
    vector<vector<int>> re;
    vector<int> path;
    int n;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);
        return re;
    }
    void dfs(vector<int>& nums, int i) 
    {
        if (i == n) 
        {
            re.push_back(path);
            return;
        }

        // 1.不选nums[i]
        dfs(nums, i + 1);
        // 2.选nums[i]
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        // 回溯
        path.pop_back();

        return;
    }
};

方法二：方法一是对每一个数进行选或者不选

方法二就是根据选数的个数来找，选0个数的组合 1个数的组合 2个数的组合...

选0个数:空集

选1个数: 1 2 3

选2个数:12 13 23

...

当我们选完一个数后，选下一个数时，只能选该数在nums数组后面的数。

eg.选了2后面只能选3 选了3后面没有数了不能继续选

1.怎么知道该数后面还有那些数？
传参数pos标记该数在nums数组中的位置，for循环遍历它后面的数

2.递归出口：
每一次进入dfs函数时，当前的path都是一次结果，存入直接返回。

class Solution {
    vector<vector<int>> re;
    vector<int> path;
    int n;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);
        return re;
    }
    void dfs(vector<int>& nums, int pos) 
    {
        re.push_back(path);
        for(int i=pos;i<n;i++)
        {
            path.push_back(nums[i]);
            dfs(nums,i+1);
            //回溯
            path.pop_back();
        }
    }
};