LeetCode 面试题08.04.幂集

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

法一：幂集有2的n次方个，我们可以从0开始循环到2的n次方减1，每次循环生成一个幂集，方法是数字中为1的位对应位置的数放入当前幂集中：

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

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

如果nums的长度为n，此算法时间复杂度为O(n2${}^n$)，一共有2${}^n$种子集，每种需要n的时间来构建；空间复杂度为O(1)。

法二：递归模拟：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> oneAns;
        build(0, nums, oneAns, ans);

        return ans;
    }

private:
    void build(int index, vector<int> &nums, vector<int> &oneAns, vector<vector<int>> &ans)
    {
        if (index == nums.size())
        {
            ans.push_back(oneAns);
            return;
        }

        oneAns.push_back(nums[index]);
        build(index + 1, nums, oneAns, ans);
        oneAns.pop_back();
        build(index + 1, nums, oneAns, ans);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

如果nums的长度为n，此算法时间复杂度为O(n2${}^n$)，空间复杂度为O(n)。

法三：先构建一个空集，每遍历到一个元素，将其加入现有的任意集合都可以构成一个新的集合：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        ans.push_back({});

        for (int i = 0; i < nums.size(); ++i)
        {
            int ansSize = ans.size();
            for (int j = 0; j < ansSize; ++j)
            {
                vector<int> temp = ans[j];
                temp.push_back(nums[i]);
                ans.push_back(temp);
            }
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

如果nums的长度为n，此算法时间复杂度为O(2${}^n$)，空间复杂度为O(1)。