首页 > 代码库 > careercup-递归和动态规划 9.4

careercup-递归和动态规划 9.4

9.4 编写一个方法,返回某集合的所有子集。

类似leetcode:Subsets

解法:

解决这个问题之前,我们先要对时间和空间复杂度有个合理的评估。一个集合会有多少子集?我们可以这么计算,生成了一个子集时,每个元素都可以“选择”在或者不在这个子集中。也就是说,第一个元素有两个选择:它要么在集合中,要么不在集合中。同样,第二个元素也有两个选择,以此类推,2相乘n次等于2^n个子集。因此,在时间和空间复杂度上,我们不可能做得比O(2^n)更好。

解法一:递归

首先将空集合加入,则当前集合为{{}}

然后将第一个元素加入当前集合的每一个子集中,并将的到的新的子集也加入到当前集合中,则有{{}{1}}

加入第二个元素时,则有{{}{1}{2}{1,2}}

加入第三个元素时,则有{{}{1}{2}{1,2}{3}{1,3}{2,3}{1,2,3}}

 

根据上面的思路,代码实现如下:

#include<iostream>#include<vector>using namespace std;vector<vector<int> > subset(vector<int> &S){    vector<vector<int> > ret;    if(S.empty())        return ret;    int n=S.size();    int i,j;    ret.push_back(vector<int>());    for(i=0;i<n;i++)    {        int m=ret.size();        for(j=0;j<m;j++)        {            vector<int> tmp=ret[j];            tmp.push_back(S[i]);            ret.push_back(tmp);        }    }    return ret;}int main(){    vector<int> res={1,2,3};    vector<vector<int> > ret=subset(res);    for(auto a:ret)    {        for(auto t:a)            cout<<t<<" ";        cout<<endl;    }    cout<<"subset sum : "<<ret.size()<<endl;}

 解法二 :组合数学

回想一下,在构造一个集合时,每个元素有两种选择(1)该元素在这个集合中(“yes”状态),或者(2)该元素不在这个集合中(“no”状态)。这就意味着每个子集都是一串yes和no,比如“yes,yes,no,no,yes,no”。

由此,总共可能会有2^n子集。怎样才能迭代变量所有元素的所有“yes”“no”序列?如果将每个“yes“视作1,每个”no“视作0,那么,每个子集就可以表示为一个二进制串。

#include<iostream>#include<vector>using namespace std;vector<vector<int> > subset(vector<int> &S){    vector<vector<int> > ret;    if(S.empty())        return ret;    int n=S.size();    int i,j;    ret.push_back(vector<int>());    for(i=0;i<n;i++)    {        int m=ret.size();        for(j=0;j<m;j++)        {            vector<int> tmp=ret[j];            tmp.push_back(S[i]);            ret.push_back(tmp);        }    }    return ret;}vector<vector<int> > subset1(vector<int> &S){    vector<vector<int> > res;    int n=1<<S.size();    int i,j;    for(i=0;i<n;i++)    {        vector<int> tmp;        int index=0;        //对每一个二进制数检查哪些位为0或1,为1的加入到tmp中,为0的不加入        for(j=i;j>0;j>>=1)        {            if(j&1)            {                tmp.push_back(S[index]);            }            index++;        }        res.push_back(tmp);    }    return res;}int main(){    vector<int> res={1,2,3};    vector<vector<int> > ret=subset1(res);    for(auto a:ret)    {        for(auto t:a)            cout<<t<<" ";        cout<<endl;    }    cout<<"subset sum : "<<ret.size()<<endl;}

 

careercup-递归和动态规划 9.4