leetcode 77. Combinations (枚举子集,限定集合大小)

Posted by 111qqz on Thursday, April 13, 2017

TOC

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

思路:就是枚举子集,根据集合的大小剪枝。。。最后只要集合大小为k的集合

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 15时25分37秒
File Name :77.cpp
************************************************ */
class Solution {
public:
    set<vector<int> >se;
    int B[1005];
    vector<vector<int> >res;
    void get_subset(int n,int *B,int cur,int cnt,int k)
    {
    if (cur==n)
    {
        vector<int>tmp;
        for ( int i = 0 ; i < n ; i++)
        if (B[i]) tmp.push_back(i+1);
        if (tmp.size()==k)
        se.insert(tmp);
        return ;
    }
    if (cnt<k)
    {
        B[cur] = 1;
        get_subset(n,B,cur+1,cnt+1,k);
    }
    B[cur] = 0 ;
    get_subset(n,B,cur+1,cnt,k);
    }
    vector<vector<int>> combine(int n, int k) {
    get_subset(n,B,0,0,k);
    for (auto &it:se)
    {
        res.push_back(it);
    }
    return res;
    }
};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付