Distância de Hamming

0110

0101

0011

Por se tratar de um problema que exige que verifiquemos todas as possibilidades, utilizar uma técnica de busca completa parece ser adequado. Mais especificamente, podemos ver a solução desse problema com o uso de backtracking.

Como o backtracking se baseia em construir a solução dando um passo e depois chamando recursivamente a solução do próximo passo, temos que identificar o que são esses passos.

Inicialmente podemos pensar que a nossa solução é um array preenchido todo com zero. Logo, o primeiro passo para chegar na solução é escolher qual posição devemos marcar como 1. No primeiro passo, podemos escolher qualquer posição para ser 1. Ou seja, se o array tem tamanho, temos n candidatos. Veja na figura abaixo que ilustramos essa situação como se estivéssemos no nó raiz. Nesse ponto, teríamos 4 candidatos: as posições 0, 1, 2 e 3 do array.

Se escolhermos o primeiro candidato, nesse caso o zero, temos ainda 3 possibilidades a serem preenchidas com o 1, que seriam as posições 1, 2 e 3.

Qual a condição de parada?

Ora, se a cada passo da recursão, colocamos um 1 na solução e o números de 1s na solução final é igual a entrada H da entrada, então, só precisamos descer na árvore H vezes. No caso do exemplo, 2 vezes.

Agora suponha que já exploramos todo o nó 0 e vamos agora analisar o outro candidato, que é o 1. Nesse caso, poderíamos pensar em gerar como possibilidades o 0, 2 e 3. Porém, se você gerar o 0 como candidato, na solução o efeito de ligar o 1 e o 0 é o mesmo que ligar o 0 e o 1. Ou seja, a ordem não importa. E como no ramo anterior já havíamos colocado o 0 e o 1 na solução, não precisamos mais gerar o 0 como candidato do 1. Esse mesmo raciocínio se repete com os outros candidatos.