题目描述

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

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

示例:

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

我的解法——DFS（AC）

对结合[1,2,3] 从0结点的1开始，都有选择或者不选，不选为空，放在左子树，选择放在由子树，这样就得到一棵完全二叉树，其中叶子结点就是我们所求。
时间复杂度O(n)，空间复杂度O(n)
Beat 56%

class Solution(object):
    def __init__(self):
        self.res = []
        self.length = 0
        
    def dfs(self, nums, now, now_res):
        if(now == self.length):
            self.res.append(now_res)
        else:
            self.dfs(nums, now + 1, now_res + [nums[now]])
            self.dfs(nums, now + 1, now_res)
            
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.length = len(nums)
        
        self.dfs(nums, 0, [])
        
        return self.res

最优解法——位运算

对于n个元素，每个元素要么加入要么不加入，则会得到一个n位的二进制串，n为二进制串可以看做是一个状态或者说一个子集，每个元素与一位一一对应，状态的大小为1«n. 对于每个状态j，我们通过判断第k位是否为1，为1则将S[k]加入vec，判断结束，将vec加入result即可。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > result;
        int n = S.size();
        int max = 1 << n;     // 最多状态数 存在用1 不存在用0
        int i = 0;
        sort(S.begin(), S.end());
        while(i < max){            // 对每一种状态进行遍历 并将其所对应的元素加入到集合中
            int j = i;
            vector<int> temp;
            /*for(int k= 0; k < n; k++){
                if((j & (1<<k)) != 0) temp.push_back(S[k]);
            }*/
            int index = 0;
            while(j>0){
                if(j&1) temp.push_back(S[index]);    // 第index为1 则加入s[index]位
                j = j >> 1;
                index++;
            }
            result.push_back(temp);
            i++;
        }
        return result;
        
    }
};

参考答案

https://blog.csdn.net/feliciafay/article/details/18976383