[数据结构与算法]LeetCode 78.子集

题目描述：(来自LeetCode)

?思路：对于每一个数组里每一个数，我们可以选择加入和不加入当前集合，n个数就有二的n次幂种可能。我们遍历数组中的每一个数，加入哪个集合呢？应该是所有已经存在的集合！！！

比如：数组：[1 2 3] 用num存当前的集合，res存所有已经存在的集合

1.res里面只有一个集合，该集合num是个空集 res[[]]

2.然后遍历数组，将res中所有已存在的集合拿出来与1组成新的集合，就是[]+1=[1],此时res[[],[1]]

?3.再遍历数组下一个元素2，将res中所有已存在的集合拿出来与2组成新的集合，就是[]+2,[1]+2,此时res[[],[1],[2],[1 2]]

4.再遍历数组下一个元素3，将res中所有已存在的集合拿出来与3组成新的集合，就是[]+3,[1]+3,[2]+3,[1 2]+3,此时res[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

可能会问？不是每种元素有两种选择吗？在这里每次都选择加入了啊？

? ? ? ? 因为在从前往后遍历的时候，没有遍历到的每一个元素都是选择不加入，而且，遍历的过程中我们一直保留了之前遍历的结果，故只要再将每一个元素加入每一个集合，就构成了每个元素加入和不加入集合的两种选择

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> num;
        vector<vector<int>> res;
        int n=nums.size();
        if(n==0) return res;
        res.push_back(num);
        for(int i=0;i<n;i++){
            int m=res.size();
            for(int j=0;j<m;j++){
               vector<int> tmp=res[j];
               tmp.push_back(nums[i]);
               res.push_back(tmp);
            }
        }
        return res;
        //[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    }
};

如有错误请指正，感谢~??