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

《程序员面试金典（第6版）》面试题 08.04. 幂集（回溯算法，位运算，C++）不断更新

article 2025/1/11 5:19:17

题目描述

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
示例:
输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题思路与代码

其实这道题，一看就是属于子集问题，让你在一个N个数的集合里有多少符合条件的子集。
回溯算法是一种试探性的搜索算法，它在解决某些组合问题，字节问题，排列问题等时非常有效，所以呢，这道题，我们就可以去用回溯法去解决。

方法一：回溯法

这里就用我最崇拜的carl哥的回溯三部曲模版，来带大家解这道题。

第一步，找出回溯函数模板返回值
第二步，确定回溯函数终止条件
第三步，回溯搜索的遍历过程

关于回溯算法的参数，一般是在写回溯逻辑的时候，发现缺哪个参数就加哪个参数的。不存在与在哪一个步骤就一定要确定好参数是啥。

这个是回溯法的大致模版

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

这道题具体的代码如下：

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> subsets(vector<int>& nums) {
        if(nums.empty()) return {};
        int begin = 0;
        int end = nums.size();
        vector<int> vec;
        result.push_back({});
        backtracking(nums,vec,begin,end);
        return result;
    }
    void backtracking(vector<int>& nums,vector<int>& vec,int begin,int end){
        if(begin >= end) 
            return;
        for(int i = begin; i < end; ++i){
            vec.push_back(nums[i]);
            result.push_back(vec);
            backtracking(nums,vec,++begin,end);
            vec.pop_back();
        }
    }
};

需要特别注意的是，在backtracking(nums,vec,++begin,end);这一行代码中，需要特别注意第二个传入参数。
这里可以写 ++ begin 与 i + 1 但是不能去写 begin + 1，这是因为，当我们使用++begin作为递归调用的参数时，begin的值在循环迭代中会被改变，而使用begin + 1作为参数时，begin的值在循环迭代中保持不变。这是它们之间的关键区别。
使用++begin能够得到正确的结果，因为它确保了begin在每次递归调用之后递增。这样，当递归返回到当前层次时，begin的值已经递增了，从而避免了重复子集的产生。
而使用begin + 1作为参数，在递归调用时虽然传递了正确的下一个值，但在循环迭代中，begin的值保持不变。这导致递归返回到当前层次时，重复使用了相同的begin值，从而产生了重复的子集。
i + 1 也能达到与++begin同样的效果，这是因为，它们之间都可以保证每次递归调用都是从当前元素的下一个元素开始，所以是对的。而不是从下一个元素开始，这将导致生成重复的子集。

在这里插入图片描述

复杂度分析

时间复杂度：
对于给定长度为n的nums数组，这段代码会生成所有可能的子集。子集的个数是2^{n，因为每个元素都有两种选择：包含在子集中或不包含。在这个实现中，我们使用回溯法遍历所有可能的子集。在最坏的情况下，我们需要遍历所有子集并将它们添加到结果集合中。因此，时间复杂度为O(2}n * n)，其中O(2^n)是遍历所有子集的时间，O(n)是在每次递归调用中复制子集到结果集合的时间。
空间复杂度：
递归栈空间：在最坏的情况下，递归栈的深度等于数组的长度n，因此递归栈空间复杂度为O(n)。
结果集合空间：有2^n 个子集。由于子集中的元素总数是固定的，即n个元素，所以实际上我们不需要将每个子集的大小计入空间复杂度。因此，结果集合的空间复杂度应为O(2^n)。

综上所述，这段代码的空间复杂度应为O(n + 2^n)。递归栈空间为O(n)，结果集合空间为O( 2^ n) 。