Leetcode: Subsets

向右看齐 2022-08-07 16:53 148阅读 0赞

题目：  
Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
    The solution set must not contain duplicate subsets.

For example,  
If S = \[1,2,3\], a solution is:

[
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

思路一：  
采用深度优先搜索

class Solution
    {
    private:
        vector<vector<int>> result;
        int maxDepth;
    private:
        //深度优先搜索
        //depth控制搜索的深度，previous是前一次搜索的结果，orgin是原始集合，start表示在origin中开始索引
        void dfs(int depth, vector<int> previous, vector<int> &origin, int start)
        {
            result.push_back(previous);//将前一次的结果加入最终结果集合
            if (depth > maxDepth) return;//如果大于最大深度，则退出
            for (int i = start; i < maxDepth; ++i)
            {
                vector<int> current(previous);
                current.push_back(origin[i]);
                dfs(depth + 1, current, origin, i + 1);
            }
        }
    public:
        vector<vector<int>> subsets(vector<int> &S)
        {
            maxDepth = int(S.size());
            result.clear();
            if (0 == maxDepth) return result;
            sort(S.begin(), S.end());
            vector<int> current;
            dfs(0, current, S, 0);
            return result;
        }
    };

思路二：  
在网络上看到这样一种思路，觉得很巧妙。对于数组中的一个数：要么存在于子集中，要么不存在。  
则有下面的代码：

class Solution
    {
    private:
        vector<vector<int>> result;
        int maxDepth;
        void dfs(int depth, vector<int> current, vector<int> &origin)
        {
            if (depth == maxDepth)
            {
                result.push_back(current);
                return;
            }
            dfs(depth + 1, current, origin);//子集中不存在origin[depth]
            current.push_back(origin[depth]);
            dfs(depth + 1, current, origin);//子集中存在origin[depth]
        }
    public:
        vector<vector<int>> subsets(vector<int> &S)
        {
            maxDepth = int(S.size());
            result.clear();
            if (0 == maxDepth) return result;
            sort(S.begin(), S.end());
            vector<int> current;
            dfs(0, current, S);
            return result;
        }
    };