从n个元素中选择k个的所有组合（包含重复元素）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

LeetCode:Combinations这篇博客中给出了不包含重复元素求组合的5种解法。我们在这些解法的基础上修改以支持包含重复元素的情况。对于这种情况，首先肯定要对数组排序，以下不再强调

修改算法1 ：按照求包含重复元素集合子集的方法LeetCode:Subsets II算法1的解释，我们知道：若当前处理的元素如果在前面出现过m次，那么只有当前组合中包含m个该元素时，才把当前元素加入组合

class Solution {

public:

    void combine(vector<int> &vec, int k) {

        if(k > vec.size())return;

        sort(vec.begin(), vec.end());

        vector<int>tmpres;

        helper(vec, 0, k, 0, tmpres);

    }

    //从vec的[start,vec.size()-1]范围内选取k个数，tmpres是当前组合

    //times是上一个元素出现的次数

    void helper(vector<int> &vec, int start, int k, int times, vector<int> &tmpres)

    {

        if(vec.size()-start < k)return;

        if(k == 0)

        {

            for(int i = 0; i < tmpres.size(); i++)

                cout<<tmpres[i]<<" ";

            cout<<endl;

            return;

        }

        if(start == 0 || vec[start] != vec[start-1])//当前元素前面没有出现过

        {

            //选择vec[start]

            tmpres.push_back(vec[start]);

            helper(vec, start+1, k-1, 1, tmpres);

            tmpres.pop_back();

            //不选择vec[start]

            helper(vec, start+1, k, 1, tmpres);

        }

        else//当前元素前面出现过

        {

            if(tmpres.size() >= times && tmpres[tmpres.size()-times] == vec[start])

            {

                //只有当tmpres中包含times个vec[start]时，才选择vec[start]

                tmpres.push_back(vec[start]);

                helper(vec, start+1, k-1, times+1, tmpres);

                tmpres.pop_back();

            }

            helper(vec, start+1, k, times+1, tmpres);

        }

    }

};

从[1,2,2,3,3,4,5]中选3个的结果如下：

修改算法2 ：同理，可以得到代码如下本文地址

class Solution {

public:

    void combine(vector<int> &vec, int k) {

        if(k > vec.size())return;

        sort(vec.begin(), vec.end());

        vector<int>tmpres;

        helper(vec, 0, k, 0, tmpres);

    }

    //从vec的[start,vec.size()-1]范围内选取k个数，tmpres是当前组合

    //times是上一个元素出现的次数

    void helper(vector<int> &vec, int start, int k, int times, vector<int> &tmpres)

    {

        if(vec.size()-start < k)return;

        if(k == 0)

        {

            for(int i = 0; i < tmpres.size(); i++)

                cout<<tmpres[i]<<" ";

            cout<<endl;

            return;

        }

        for(int i = start; i <= vec.size()-k; i++)

        {

            if(i == 0 || vec[i] != vec[i-1])//当前元素前面没有出现过

            {

                times = 1;

                //选择vec[i]

                tmpres.push_back(vec[i]);

                helper(vec, i+1, k-1, 1, tmpres);

                tmpres.pop_back();

            }

            else//当前元素前面出现过

            {

                times++;

                //vec[i]前面已经出现过times-1次

                if(tmpres.size() >= times-1 && tmpres[tmpres.size()-times+1] == vec[i])

                {

                    //只有当tmpres中包含times-1个vec[i]时，才选择vec[i]

                    tmpres.push_back(vec[i]);

                    helper(vec, i+1, k-1, times, tmpres);

                    tmpres.pop_back();

                }

            }

        }

    }

};

修改算法3 ：算法3是根据LeetCode:Subsets 算法2修改未来，同理我们也修改LeetCode:SubsetsII 算法2

class Solution {

public:

    void combine(vector<int> &vec, int k) {

        if(k > vec.size())return;

        sort(vec.begin(), vec.end());

        vector<vector<int> > res(1);//开始加入一个空集

        int last = vec[0], opResNum = 1;//上一个数字、即将要进行操作的子集数量

        for(int i = 0; i < vec.size(); ++i)

        {

            if(vec[i] != last)

            {

                last = vec[i];

                opResNum = res.size();

            }

            //如果有重复数字，即将操作的子集的数目和上次相同

            int resSize = res.size();

            for(int j = resSize-1; j >= resSize - opResNum; j--)

            {

                res.push_back(res[j]);

                res.back().push_back(vec[i]);

                if(res.back().size() == k)//找到一个大小为k的组合

                {

                    for(int i = 0; i < res.back().size(); i++)

                        cout<<res.back()[i]<<" ";

                    cout<<endl;

                }

            }

        }

    }

};