алгоритм надмножества, использующий stl, дающий дубликаты подмножеств
Я пытаюсь найти надмножество данного вектора. Я делаю это рекурсией. Идя итеративно, я удаляю значение и затем вызываю функцию с новым набором. Я получаю все комплекты, но они повторяются. Например, для 5 элементов должно быть от 32 до 31 подмножества, в то время как я получаю около 206 подмножеств.
Это мой код
using namespace std;
int iter = 1;
void display(vector<int> &v)
{
cout<<"case#"<<iter++<<": ";
vector<int>::iterator i;
for(i=v.begin();i!=v.end();i++)
cout<<*i<<" ";
cout<<endl;
}
void gen( vector<int> &v)
{
if(v.size()==0) return;
display(v);
vector<int>::iterator j,i;
for(i=v.begin();i!=v.end();i++)
{
vector<int> t(v);
j = find(t.begin(),t.end(),*i);
t.erase(j);
gen(t);
}
}
Решение
Вам не нужно каждый раз передавать v в качестве аргумента. Просто сделайте это глобальным.
И попробуйте каждую комбинацию, чтобы найти все подмножество.
Сложность: 2 ^ N
vector<int>v;
int iter = 1;
int take[20];
void display()
{
cout<<"Case#"<<iter++<<": ";
int n=v.size();
for(int i=0;i<n;i++)
{
if(take[i])
cout<<v[i]<<" ";
}
cout<<endl;
}
void gen(int x)
{
if(x==v.size())
{
display();
return;
}
int i,j,n=v.size();
take[x]=1;
gen(x+1);
take[x]=0;
gen(x+1);
}
int main()
{
int i,j,n;
cin>>n;
for(i=0;i<n;i++)
{
cin>>j;
v.push_back(j);
}
gen(0);
return 0;
}
Другие решения