Занятие 3

Генерация всех подмножеств

Требуется сгенерировать все подмножества множества {1, …, `n`}
Вариант с битами

int i, j, n;
for(i=0; i<(1<<n); ++i)
{ for(j=0; j<n; ++j)
    if(i&(1<<j))
      printf(" %d",j+1);
  printf("\n");
}

Рекурсивный вариант

int n;
int b[100]; // массив флагов: b[i]==1 если (i+1) входит в множество
void rec(int i)
{ if(i==n)
  {
    for(i=0; i<n; ++i)
      if(b[i])
        printf(" %d",i+1);
    printf("\n");
    return;
  }
  b[i]=0;
  rec(i+1);
  b[i]=1;
  rec(i+1);
}