产生子集递归

Question

我试图生成大小3的具体布尔向量中的所有可能的子集所以应该有8项可能的子集：

#include<iostream> 
#include<fstream> 
#include<string> 
#include<stdio.h> 
#include<stdlib.h> 
#include<vector> 

using namespace std; 
int n = 3; 
int mis(vector<bool> f,int i){ 
     for(int j=0; j <f.size();j++) 
      cout<<f[i]<<" "; 
     cout<<endl; 
     f[i] = false; 
     return mis(f,i+1); 
     f[i] = true; 
     return mis(f,i+1); 
} 

int main(){ 
    vector<bool> f; 
    f.resize(n); 
    int m = mis(f,0); 
} 

，我发现了以下错误：

a.out: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed. 
Aborted 

Answer 1

实际上您犯了一些错误。在这里，正确的代码：

#include<iostream> 
#include<fstream> 
#include<string> 
#include<stdio.h> 
#include<stdlib.h> 
#include<vector> 

using namespace std; 

int n = 3; 

int mis(vector<bool> f, int i) 
{ 
    if (i > n) 
    { 
     return 0; 
    } 
    else if (i == n) 
    { 
     for(int j = 0; j < n; j += 1) 
     { 
      cout << f[j] << " "; 
     } 
     cout << endl; 
     return 1; 
    } 

    f[i] = false; 
    int a = mis(f, i + 1); 

    f[i] = true; 
    int b = mis(f, i + 1); 

    return a + b; 
} 

int main() 
{ 
    vector<bool> f(n); 
    int m = mis(f, 0); 

    cout << "Total: " << m << endl; 
} 

1. 在这种打印的vector内容的循环使用可变j但打印f[i]。我相信这是你得到断言的原因。

2. 代码f[i] = true; return mis(f, i + 1);无法访问。您应该使用变量来记住中间结果，就像我一样。

3. 递归没有退出。你永远不会检查i是否太大。

Answer 2

您没有递归的基本情况。打印endl后，您需要检查您是否完成：

... 
cout << endl; 
if (i == n) 
    return; 
...