题目描述

题目链接

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

样例

1
2
3
4
示例 1：

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

输入：nums = [0]
输出：[[],[0]]

算法1

(递归搜索) O(n⋅2n)O(n·2^n)

针对数组中的每一个数字，都有两种选择方案：选这个数或不选这个数

那么我们从第 i = 0 位开始枚举 nums 中的所有数字，当我们枚举至 i = n 时，说明所有的情况都已经枚举结束，返回当前的选择

C++ 代码

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
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<bool> st;
    vector<vector<int>> subsets(vector<int>& nums) {
        st = vector<bool> (11, false);

        dfs(nums, 0);

        return res;
    }

    void dfs(vector<int>& nums, int u)
    {
        if (u == nums.size())
        {
            res.push_back(path);

            return ;
        }

        dfs(nums, u + 1); // 不选第 u 个数

        path.push_back(nums[u]);
        dfs(nums, u + 1); // 选第 u 个数
        path.pop_back();
    }
};

算法2

(二进制优化)) O(n⋅2n)O(n·2^n)

使用 二进制 的思想对其进行优化后，虽说枚举的方案数量没有改变，但是不用递归而使用迭代，能够有效减少递归栈的空间开销

算法思想：
针对每个数，有 选 与 不选 两种方案，那么总共的方案数就为 2n2^n 种，那么我们就可以用二进制位上的 0 表示当前位置的数字不选， 1 表示当前位置的数字选择

仅通过遍历从 i=0i = 0 (所有数都不选) 到 i=2ni = 2^n (所有数都选)，依次对比每一位的 0、1情况，即可得到所有方案

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for(int i = 0; i < 1 << n; i ++)
        {
            vector<int> path;
            for(int j = 0; j < n; j ++)
            {
                if( i >> j & 1) //当前位置为 1，选
                    path.push_back(nums[j]);
            }
            res.push_back(path);
        }

        return res;
    }
};