首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode: Subsets

Leetcode: Subsets

作者头像
卡尔曼和玻尔兹曼谁曼
发布2019-01-22 15:25:07
2980
发布2019-01-22 15:25:07
举报

题目: 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;
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015年04月20日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档