P*******b 发帖数: 1001 | 1 Input an integer array of size n and an integer k (k<=n), output all subsets
of size k.
thanks | z****n 发帖数: 1379 | 2 用二进制
比如10011就是n=5,k=3的一种情况,相当于取第1个,第4个,和第5个构成subset
subsets
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Input an integer array of size n and an integer k (k<=n), output all subsets : of size k. : thanks
| d**********o 发帖数: 279 | 3
我觉得楼主是想要一个枚举的策略吧,
【在 z****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用二进制 : 比如10011就是n=5,k=3的一种情况,相当于取第1个,第4个,和第5个构成subset : : subsets
| f*********5 发帖数: 576 | 4 almost the same as get combination.
but not output everyone,just output when there is K items
subsets
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Input an integer array of size n and an integer k (k<=n), output all subsets : of size k. : thanks
| t****a 发帖数: 1212 | 5 # Subset(k, n) = 1, if k == n
# Subset(1, n) = n
# Subset(k, n) = # Subset(k, n-1) + # Subset(k-1, n-1) | s*********t 发帖数: 1663 | 6 std::vector > kSubset( std::vector& S, int start, int
k )
{
std::vector > subs;
std::vector a;
if( k == 0 || (int)S.size() - start < k){
return subs;
}
if( S.size()-start == 1 ){
a.push_back(S[start]);
subs.push_back(a);
return subs;
}
std::vector > s1 = kSubset(S, start+1, k-1);
if(s1.size()==0){
a.push_back(S[start]);
subs.push_back(a);
}
else{
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Input an integer array of size n and an integer k (k<=n), output all subsets : of size k. : thanks
| i*****e 发帖数: 113 | 7 我的解法,楼上有解法,我纯粹做练习的
S(n, k) = S(n-1, k-1) + S(n-1, k)
const int array[LEN]; // global or class member
std::list*> result; // global or class member
void enumerate(int k, int start, const vector& part)
{
if (part.size() == k) { // part.size() is unlikely greater than k
result.push(new vector(part));
return;
}
if (start >= LEN) {
return;
}
vector* v = new vector(part);
v->push_back(array[start]);
enumerat |
|