题解 | #集合的所有子集(一)#

集合的所有子集(一)

http://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9

1. 递归

每次递归,当前位置的数字可以选择或者不选择。

class Solution {
public:
    vector<vector<int> > res;
    void dfs(vector<int>& S, vector<int> tmp, int start){
        res.push_back(tmp);
        if(start == S.size()){
            return;
        }
        for(size_t i = start; i < S.size(); i++){
            tmp.push_back(S[i]);
            dfs(S, tmp, i + 1);
            tmp.pop_back();
        }
    }
    
    vector<vector<int> > subsets(vector<int> &S) {
        if(S.empty()) return res;
        sort(S.begin(), S.end());
        dfs(S, vector<int>(), 0);
        return res;
    }
};

2. 位运算:n个元素的子集共有2^n个.

将0~2^n-1的每一个数转换为n位的二进制数来看,如果第0~n-1的某一位为1,则选择对应位置的数。遍历完即可获得所有子集。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > res;
        vector<int> tmp;
        int n = S.size();
        if(S.empty()) return res;
        sort(S.begin(), S.end());
        for(int i = 0; i < pow(2, n); i++){
            for(int j = 0; j < n; j++){
                if((i >> j) & 1){
                    tmp.push_back(S[j]);
                }
            }
            res.push_back(tmp);
            tmp.clear();
        }
        return res;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务