Leetcode: Subsets-蒲公英云

Leetcode: Subsets

向右看齐 2022-08-07 16:53 244阅读 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;
    }
};