描述

现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素

数据范围：1 \le n \le 51≤n≤5，集合中的任意元素满足 |val| \le 10∣val∣≤10
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

示例1

输入： 
[1,2,3]
复制
返回值： 
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
复制

示例2

输入： 
[]
复制
返回值： 
[]
复制
解题思路：
1、本题与全排列类似，全排列要输出的所有元素的所有排列方式，而本题需要输出所有的子集；
2、要输出子集，首先要在递归算法中修改遍历起始位置为当前元素的下一个元素，而不是从0开始遍历；
3、注意题目的输出要求“你给出的子集中的元素必须按升序排列”这个升序并不是字典树的升序，而是个数的升序、个数相同时按字典树的升序；
4、故使用数字k，在递归算法中统计tmp中的数据个数等于k后将tmp加入结果数组。 
class Solution {
public:
    vector<vector<int> >res;
    vector<int> tmp;
    void dfs(vector<int> &S, int k, int index) {
        if (k == tmp.size()) {
            res.push_back(tmp);
        }
        
        int n = S.size();
        for (int i = index; i < n; i++) {
            tmp.push_back(S[i]);
            dfs(S, k, i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int> > subsets(vector<int> &S) {
        
        sort(S.begin(), S.end());
        // 这个for循环是用来控制输出的子集元素的个数，可以理解为分别输出个数为k的子集
        for (int k = 0; k <= S.size(); k++) {
            dfs(S, k, 0);
        }
        return res;
    }

};