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

给出的解集中不能出现重复的元素

#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > subsets(vector<int>& S) {
        // write code here 迭代
        vector<vector<int>> ans;
        ans.push_back({});

        for (int i = 0; i < S.size(); i++) {

            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> row(ans[j]);
                row.push_back(S[i]);
                sort(row.begin(), row.end());
                ans.push_back(row);
            }

        }
        //sort(ans.begin(), ans.end());
        return ans;
    }
};

算法基本思想：

利用迭代的方式，每次将一个新的元素加入到已有的子集中，生成新的子集。

时间复杂度：

O(2^n * nlogn)，其中n为数组S的长度，2^n为所有子集的个数，nlogn为每次加入新元素时需要排序的时间复杂度。

空间复杂度：

O(2^n * n)，需要存储所有子集的空间。

二、现在有一个整数集合S，里面可能存在重复的元素（在一的基础上加栈去重）

#include <algorithm>
#include <stack>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > subsets(vector<int>& nums) {
        // write code here

        vector<vector<int>> ans;
        ans.push_back({});

        for (int i = 0; i < nums.size(); i++) {
            
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                vector<int> row(ans[j]);
                row.push_back(nums[i]);
                sort(row.begin(), row.end());
                ans.push_back(row);
            }
        }
        //前面的就是集合的所有子集（一）
        //加个数组栈去重一下就好了
        stack<vector<int>> s;
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) {
            if (s.empty() || s.top() != ans[i]) {
                s.push(ans[i]);
            }
        }
        
        vector<vector<int>> ans2;
        while (!s.empty()) {
            ans2.push_back(s.top());
            s.pop();
        }

        sort(ans2.begin(), ans2.end());
        return ans2;
    }
};

算法基本思想：

利用迭代的方式，每次将一个新的元素加入到已有的子集中，生成新的子集。然后使用一个栈去重。

时间复杂度：

O(2^n * nlogn)，其中n为数组nums的长度，2^n为所有子集的个数，nlogn为每次加入新元素时需要排序的时间复杂度。

空间复杂度：

O(2^n * n)，需要存储所有子集的空间。