分析

• 本题的考点：位运算。

• 如果nums中有n个元素，则其子集的个数为$2^n$个。

• 我们可以使用一个二进制数据mask中的后n位表示nums数组中的每个元素是否被选择，如果mask & (1 << i)是1的话，表示nums[i]在当前的子集中。

• 我们让mask从0循环到(1 << n) - 1就可以得到所有子集，每个不同的mask值对应一个子集。

代码

• C++

class Solution {
public:
    vector<vector<int>> subsets(vector<int> &nums) {

        vector<vector<int>> res;
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> p;
            for (int i = 0; i < n; i++)
                if (mask & (1 << i))
                    p.push_back(nums[i]);
            res.push_back(p);
        }
        return res;
    }
};

• Java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {

        ArrayList<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> p = new ArrayList<>();

        int n = nums.length;
        for (int mask = 0; mask < (1 << n); mask++) {
            p.clear();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0)
                    p.add(nums[i]);
            }
            res.add(new ArrayList<>(p));
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(2^n)$，n为数组长度。

• 空间复杂度：考虑存储结果的数组 $O(2^n \times n)$。