题意分析

  • 给你一个序列，需要找到这个序列的所有的子序列的集合，要求这些子序列的内部需要按照元素的大小进行升序排列。
  • 前置知识
    • 什么是子序列？子序列是一个序列里面选择若干个元素，这些元素要保持初始的相对位置，然后组成的一个新的序列就叫做这个初始序列的子序列。

思路分析

解法一 回溯法

  • 对于每个元素，我们知道，有选择和不选的区别，这其实就是一个很明显的递归的操作。所以我们可以使用回溯法进行求解。我们按照顺序遍历这个序列，这是为了保持数据的升序。然后，当我们收集到某一个元素的时候，我们需要在进行完这一次DFS的时候进行回溯，就是不选择这个元素继续进行递归处理。

  • 代码如下

    • 递归操作，需要选择到每个位置，时间复杂度为O(2^n)
    • 利用了一个unordered_map进行哈希处理，同时使用了一个全局vector，空间复杂度为O(n) 
class Solution {
public:
    vector<vector<int> > ans;
    unordered_map<vector<int>,bool> mp;
    vector<int> v;
    int n;
    void dfs(int cnt,vector<int> &S){
        // 如果这个数组之前没有出现过，那么记录下来
        if(mp[v]==false){
            ans.push_back(v);
            mp[v]=true;
        }
        // 递归出口
        if(cnt==n){
            return;
        }
        dfs(cnt+1,S);
        v.push_back(S[cnt]);
        dfs(cnt+1,S);
        // 回溯
        v.pop_back();
    }
    vector<vector<int> > subsets(vector<int> &S) {
        n=S.size();
        // 由于子集需要升序排列，所以先进行排序
        sort(S.begin(),S.end());
        dfs(0,S);
        return ans;
    }
};

解法二 迭代

  • 这个思想是比较巧妙地一个思想，由于最初始的序列保持了元素的升序，那么我们可以按照顺序进行迭代，当然，我们首先需要将一个空的序列放入最终的答案，然后我们每次添加一个元素，就相当于在目前已知的所有的序列里面新添加一个元素，这就是本题迭代的思想。
  • 具体请看下图的过程。

图片说明

  • 代码如下
    • 我们对于每个元素的迭代的此时为O(1+2+3+4+..+n)=O()，但是，我们看在第二重循环里面还有一个vector的直接赋值，那么这里也是,即时间复杂度为
    • 程序中途使用了一个tmp进行处理，空间复杂度为O(n) 
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > ans;
        ans.push_back({});
        // 大循环枚举为了保证元素是按照升序排列
        for(auto x:S){
            int n=ans.size();
            // 小循环枚举是为了在这个x添加进来之后更新之前全部的序列
            for(auto i=0;i<n;i++){
                vector<int> tmp(ans[i]);
                tmp.push_back(x);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};