LeetCode 剑指 Offer II 079. 所有子集

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

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

示例 1：

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

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解法一：如果输入数组大小为n，则子集数量为2${}^n$，我们可以从0循环到2${}^n$-1，对于循环到的每个数字i，其中二进制位为1的位对应输入数组中的元素加入到当前子集中：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {int sz = nums.size();int subSetsNum = pow(2, sz);vector<vector<int>> ans;for (int i = 0; i < subSetsNum; ++i) {vector<int> cur;for (int j = 0; j < sz; ++j) {if ((1 << j) & i) {cur.push_back(nums[j]);} }ans.push_back(cur);}return ans;}
};

如果输入数组大小为n，此算法时间复杂度为O（n*2${}^n$），空间复杂度为O（n）。

解法二：递归处理，每处理到一个元素时，有两种处理方法，将其加入子集或不加入子集：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> current;recursion(0, nums, current, ans);return ans;}private:void recursion(int pos, vector<int> &nums, vector<int> &current, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(current);return;}// 不加当前位置元素recursion(pos + 1, nums, current, ans);// 加当前位置元素current.push_back(nums[pos]);recursion(pos + 1, nums, current, ans);current.pop_back();}
};

如果输入数组大小为n，此算法时间复杂度为O（n*2${}^n$），一共有2${}^n$种子集，每种需要O（n）的时间加入结果数组ans，空间复杂度为O（n），主要是栈空间开销和current数组开销。