LeetCode:Combinations这篇博客中给出了不包含重复元素求组合的5种解法。我们在这些解法的基础上修改以支持包含重复元素的情况。对于这种情况，首先肯定要对数组排序，以下不再强调
修改算法1：按照求包含重复元素集合子集的方法LeetCode:Subsets II算法1的解释，我们知道：若当前处理的元素如果在前面出现过m次，那么只有当前组合中包含m个该元素时，才把当前元素加入组合
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
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：同理，可以得到代码如下 本文地址
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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;
}
}
}
}
}; |
对于算法4和算法5，都是基于二进制思想，这种解法不适用与包含重复元素的情况
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3695463.html，如需转载请自行联系原作者