穷举vs暴搜vs深搜vs回溯vs剪枝（一）

文章目录

全排列
子集
找出所有子集的异或总和再求和
全排列 II
电话号码的字母组合

全排列

题目：全排列

在这里插入图片描述

思路

通过深度优先搜索的方式，不断枚举每个数在当前位置的可能性，然后回溯到上一个状态，直到枚举完所有可能性得到正确的结果

在这里插入图片描述

res：一个二维向量vector<vector<int>>，用于存储所有生成的排列。
path：一个一维向量vector<int>，用于存储当前正在构建的排列。
check：一个布尔数组bool check[7]，用于标记数组nums中的每个元素是否已经被用于当前排列中。这里假设nums数组的大小不会超过6（因为数组索引从0开始，最大索引为6时，数组大小为7）。
递归的终止条件是path的大小等于nums的大小。
在递归过程中，使用check数组来确保不会重复使用同一个元素。
使用path.push_back(nums[i])和path.pop_back()来实现回溯，即在尝试下一个元素之前，需要将当前元素从path中移除，以便尝试其他可能的元素组合。
通过check[i] = true和check[i] = false来标记元素是否已被使用。

C++代码

class Solution 
{
    vector<vector<int>> res;
    vector<int> path;
    bool check[7];

public:
    void dfs(vector<int>& nums)
    {
        if(nums.size() == path.size())
        {
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i ++ )
        {
            if(!check[i])
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯 -> 恢复现场
                path.pop_back();
                check[i] = false;
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) 
    {
        dfs(nums);
        return res;
    }
};

子集

题目：子集

在这里插入图片描述

思路1

在这里插入图片描述

我们先将所有结果个数为1的选出来，再再其基础上选出结果个数为2的，依次类推

从 pos 开始遍历 nums 数组。对于每个位置 i ，执行以下操作：
将 nums[i] 添加到 path 中。
递归调用 dfs 函数，以 i + 1 作为新的起始位置，继续搜索。
在递归调用返回后，进行回溯操作：将刚刚添加到 path 中的 nums[i] 移除，以便尝试其他可能的元素组合（或停止进一步搜索）。

C++代码

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();
        }
    }
};

思路2

在这里插入图片描述

依次枚举，1选不选，选的话在1基础上2选不选，选的话在2基础上选不选，枚举出所有结果；当当前位置等于数组大小时，将结果加入答案中

首先检查pos是否等于nums的大小。如果是，说明已经遍历到数组的末尾，此时path代表了一个完整的子集（可能是空集，也可能是包含数组所有元素的集合，这取决于dfs的调用过程）。然后，将这个子集添加到ret中，并返回
将nums[pos]添加到path中，然后递归调用dfs函数，以pos + 1作为新的起始位置继续搜索。在递归调用返回后，执行回溯操作：从path中移除nums[pos]，以便尝试其他可能的元素组合或停止进一步搜索。

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) 
    {
        if (pos == nums.size()) 
        {
            ret.push_back(path);
            return;
        }

        path.push_back(nums[pos]);
        dfs(nums, pos + 1);
        path.pop_back();

        dfs(nums, pos + 1);
    }
};

找出所有子集的异或总和再求和

题目：找出所有子集的异或总和再求和

在这里插入图片描述
思路

本题和上题思路一样，我们使用上题的第一种思路，依次枚举，1选不选，选的话在1基础上2选不选，选的话在2基础上选不选；
不同的是将每个子集的值异或，并将其相加

从数组的第一个元素开始，递归地构建所有可能的子集
在每个递归步骤中，可以选择包含当前元素（通过异或操作更新path）或不包含当前元素（直接递归到下一个位置）
int path选择1将其异或在path上，再选2异或在path上；
当到达数组的末尾时，将当前的 path（即当前子集的异或和）加到 res 上

C++代码

class Solution 
{
    int path;
    int res;
public:
    void dfs(vector<int>& nums, int pos)
    {
        res += path;
        for(int i = pos; i < nums.size(); i ++ )
        {
            path ^= nums[i];
            dfs(nums, i + 1);
            path ^= nums[i];
        }

    }
    int subsetXORSum(vector<int>& nums) 
    {
        dfs(nums, 0);
        return res;
    }
};

全排列 II

题目：全排列 II

在这里插入图片描述
思路

同一个节点的分支中，相同的元素只能选择一次
同一个数只能使用一次

只关心不合法分支

if(cheak[i] == true) || (i != 0 && nums[i] == nums[i-1] && cheak[i-1] == false))

C++代码

class Solution 
{
    vector<int> path;
    vector<vector<int>> ret; 
    bool check[9];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }

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

        for(int i = 0; i < nums.size(); i++)
        {
            if(check[i] == true|| (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) 
                continue;
            path.push_back(nums[i]);
            check[i] = true;
            dfs(nums, pos + 1);
            path.pop_back();
            check[i] = false;
        }

    }
};

只关心合法分支

if(cheak[i] == false) && (i == 0 || nums[i] != nums[i-1] ||cheak[i-1] != false))

C++代码

class Solution 
{
    vector<int> path;
    vector<vector<int>> ret; 
    bool check[9];
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        if(pos == 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] != false)) 
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums, pos + 1);
                path.pop_back();
                check[i] = false;
            }
        }

    }
};

电话号码的字母组合

题目：电话号码的字母组合

在这里插入图片描述
思路

利用一个全局的字符串数组来帮我映射数组和字母之间的关系

如果pos等于digits的长度，说明已经处理完所有数字，将当前的path（即一个完整的字母组合）添加到结果数组ret中，并返回
否则，对于当前数字digits[pos]，遍历其对应的所有字母（通过str[digits[pos] - '0']访问。对于每个字母，执行以下操作
- 将当前字母添加到path的末尾。
- 递归调用dfs函数，处理下一个数字pos + 1。
- 在递归返回后，将刚刚添加的字母从path中移除，以便尝试当前数字对应的下一个字母。

C++代码

class Solution 
{
    vector<string> ret;
    string path;
    string str[10]={"",
        "", "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 : str[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};