修改算法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,都是基于二进制思想,这种解法不适用与包含重复元素的情况
【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3695463.html
从n个元素中选择k个的所有组合(包含重复元素),布布扣,bubuko.com
原文:http://www.cnblogs.com/TenosDoIt/p/3695463.html