Backtracking

Backtracking
- Recursão com mais de uma direção de busca.
Ex.: Imprimir na tela todas as combinações de 0 e1 de tamanho 3.

void combinacao(int *vet, int pos)
{
if(pos==3) { int i; for(i=0;i<3;i++) printf("%d",vet[i]); printf("\n"); } else { vet[pos]=0; combinacao(vet,pos+1); vet[pos]=1; combinacao(vet,pos+1); }
}

void combinacao(int *vet, int pos)
{
if(pos==3) { int i; for(i=0;i<3;i++) printf("%d",vet[i]); printf("\n"); } else { int i; for(i=0;i<=1;i++) { vet[pos]=1; combinacao(vet,pos+1) } }
}

Faça uma programa que imprima na tela todas as combinações, de tamanho N, de 6,7 e 8. void combinacao(int *vet, int pos,int n)
{
if(pos==n) { int i; for(i=0;i<n;i++) printf("%d",vet[i]); printf("\n"); } else { int i; for(i=6;i<=8;i++) { vet[pos]=i; combinacao(vet,pos+1,n) } }
}

Combinação com 1,4 e 9:

void combinacao(int *vet, int pos, int n,int *vetaux)
{
if(pos==n) { int i; for(i=0;i<n;i++) printf("%d",vet[i]); printf("\n"); } else { int i; for(i=6;i<=8;i++) { vet[pos]=vetaux[i]; combinacao(vet,pos+1,n,vetaux) } }
}

Imprima todas as combinações de 0 e 1. De tal forma que o elemento do meio do vetor seja igual a zero.

void combinacao(int *vet, int pos,int n)
{
if(pos==n) { int i; if(vet[n/2]==0) for(i=0;i<n;i++) printf("%d",vet[i]); printf("\n"); } else { int i; for(i=0;i<=1;i++) { vet[pos]=1; combinacao(vet,pos+1,n); } }
}

Trabalho
1- Imprima todas as combinações e 0 e 1, tal que o número de 0 seja maior que número de 1.
2- Conte todas as combinações de 1,4 e 9. Tal que exista mais 9 do que qualquer outro elemento.
3- Imprima na tela todas as combinações de “a e i o u”.
4- Considere um conjunto A={a, e, i}. Imprima na tela todos os seus subconjuntos. (sem repetições)
5- Suponha moedas de 1,2,5,10. Deseja-se saber de quais maneiras diferentes moedas de 1,2,5,e 10 podem ser somadas para totalizar um valor X fornecido.
6-