Gerando todos os subconjuntos

Para resolver alguns tipos de problemas, precisamos construir de um algoritmo para gerar todos os subconjuntos para encontrar subconjunto em particular que satisfaz uma dada propriedade.

O algoritmo para construir todos os subconjuntos pode ser usado em algoritmo de busca  exaustiva que consiste em enumerar explicitamente todas os subconjuntos e testá-los   e/ou em um algoritmo de enumeração implícita.

Algoritmo para gerar todos os subconjuntos

#include <stdio.h>
#include <stdlib.h>
int conj[32];
int cont;
void subconjunto(int i, int n){
 int j;
 if(i>n){
  printf("%d subconjunto:",++cont);
  for(j=1;j<=n;j++)
   if(conj[j]==1)
    printf("%d ",j);
  printf("\n");
 }else{
  conj[i] = 1;
  subconjunto(i+1,n);
  conj[i] = 0;
  subconjunto(i+1,n);
 }
}

int main(){
 int n;
 scanf("%d",&n);
 cont = 0;
 subconjunto(1,n);
 return 0;
}

Saída

3
1 subconjunto:1 2 3
2 subconjunto:1 2
3 subconjunto:1 3
4 subconjunto:1
5 subconjunto:2 3
6 subconjunto:2
7 subconjunto:3
8 subconjunto:



Tabela da execução do algoritmo

Gerando todos os subconjunto usando bitsmask
Algoritmo para gerar todos os subconjuntos

#include <stdio.h>
#include <stdlib.h>

int main(){
 int n,i,j;
 scanf("%d",&n);
 
 for(i=0;i<(1<<n);i++){
  printf("subconjunto %d: ",i);
  for(j=0;j<n;j++){
   if((i & (1<<j))!= 0){
    printf("%d ",j+1);
   }
  }
  printf("\n");
 }
 return 0;
}

Saída

3
subconjunto 0:
subconjunto 1: 1
subconjunto 2: 2
subconjunto 3: 1 2
subconjunto 4: 3
subconjunto 5: 1 3
subconjunto 6: 2 3
subconjunto 7: 1 2 3