题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

样例

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

算法1

(DFS) $O(2 ^ n)$

枚举方案，使用DFS枚举即可。

时间复杂度

时间复杂度为子集个数，即$O(2^n)$

参考文献

C++ 代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {};
        dfs(nums, 0);
        return res;
    }

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

        for (int i = idx; i < nums.size(); ++i){
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};

算法2

(二进制枚举) $O(2^n)$

使用二进制的每一位表示nums中的元素是取还是不取，将$2^n$个数对应的子集存入答案。

时间复杂度

时间复杂度为子集个数，即$O(2^n)$

参考文献

C++ 代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {};
        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) 
                    path.push_back(nums[j]);

            res.push_back(path);
        }

        return res;
    }
};