Algoritmos de backtracking são uma técnica poderosa para resolver problemas que envolvem a exploração de todas as combinações ou permutações possíveis para encontrar soluções. Eles são particularmente úteis quando a profundidade da busca (por exemplo, o comprimento de uma string a ser gerada) não é fixa, tornando abordagens iterativas simples impraticáveis. O backtracking constrói soluções passo a passo, e quando uma solução parcial não pode ser estendida para uma solução completa, ele "retrocede" para tentar uma alternativa.

A essência do backtracking reside na recursão. Ao invés de pensar em múltiplas camadas de loops para construir uma estrutura, pensamos em um problema original (construir uma estrutura de tamanho N) e como ele se relaciona com um subproblema (construir uma estrutura de tamanho N-1). Uma função recursiva, muitas vezes chamada de DFS (Busca em Profundidade), gerencia esse processo.

Combinações de Letras de um Número de Telefone

Conisdere o problema de gerar todas as combinações de letras que um determinado número de telefone pode representar. Cada dígito (de 2 a 9) corresponde a um conjunto de letras. Por exemplo, '2' corresponde a "abc", '3' a "def", e assim por diante.

Lógica de Backtracking

Para resolver isso com backtracking, podemos pensar em construir a combinação letra por letra. A cada passo, para o dígito atual, iteramos por todas as letras possíveis associadas a ele. Adicionamos uma letra à nossa combinação parcial e então chamamos recursivamente a função para o próximo dígito. Se chegarmos ao final de todos os dígitos, significa que uma combinação completa foi formada, e a adicionamos aos resultados. Após a chamada recursiva, desfazemos a escolha para explorar outras possibilidades (embora neste problema específico, a restauração do estado seja implícita ao construir uma nova string ou ao usar um array de caminho com índice).

Exemplo de Código (Python)

class Solution:
   def combinacoesLetras(self, digitos: str) -> list[str]:
       # Mapeamento de dígitos para letras correspondentes
       MAPA_DIGITOS = {
           '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
           '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"
       }

       num_digitos = len(digitos)
       if num_digitos == 0:
           return []

       resultados_finais = []
       caminho_atual = [''] * num_digitos # Array para construir a combinação

       def explorar_caminhos(indice_digito_atual: int):
           # Condição base: se processamos todos os dígitos, adicionamos a combinação
           if indice_digito_atual == num_digitos:
               resultados_finais.append("".join(caminho_atual))
               return

           # Obtemos o dígito atual e suas letras correspondentes
           digito = digitos[indice_digito_atual]
           letras_possiveis = MAPA_DIGITOS[digito]

           # Iteramos por cada letra possível para o dígito atual
           for letra in letras_possiveis:
               caminho_atual[indice_digito_atual] = letra # Faz a escolha
               # Chamada recursiva para o próximo dígito
               explorar_caminhos(indice_digito_atual + 1)
               # Não é necessário `pop()` aqui, pois `caminho_atual` é sobrescrito no próximo loop
               # e a cópia da string é feita no final.

       explorar_caminhos(0) # Inicia a exploração a partir do primeiro dígito
       return resultados_finais

Complexidade

A complexidade de tempo para este problema é aproximadamente O(N * 4^N), onde N é o número de dígitos. O fator 4^N surge porque o dígito '7' e '9' têm 4 letras, representando o pior caso para as ramificações recursivas. O fator N é devido ao custo de criar uma nova string (juntando os caracteres em caminho_atual) a cada vez que uma combinação completa é encontrada.

Gerando Subconjuntos de um Conjunto

Um problema clássico de backtracking é encontrar todos os subconjuntos possíveis de um conjunto dado de números (sem duplicatas). Por exemplo, para [1, 2], os subconjuntos são [], [1], [2], [1, 2].

Existem duas abordagens comuns de backtracking para este problema:

Abordagem 1: Escolher ou Não Escolher um Elemento

Para cada elemento no conjunto de entrada, temos duas opções: incluí-lo no subconjunto atual ou não incluí-lo. Podemos modelar isso recursivamente.

Lógica de Backtracking

Começamos com o primeiro elemento. Fazemos uma chamada recursiva sem incluí-lo (explorando o caminho onde ele não é parte do subconjunto). Em seguida, incluímos o elemento na nossa construção parcial e fazemos outra chamada recursiva (explorando o caminho onde ele é parte do subconjunto). Uma vez que todas as opções para um elemento foram exploradas, precisamos "desfazer" a inclusão dele para que as chamadas recursivas anteriores possam continuar expolrando outros caminhos.

Exemplo de Código (Python)

class Solution:
   def todosSubconjuntos(self, elementos: list[int]) -> list[list[int]]:
       num_elementos = len(elementos)
       resultados_finais = []
       subconjunto_temporario = [] # Armazena o subconjunto sendo construído

       def gerar_subconjuntos_recursivo(indice_atual: int):
           # Condição base: se processamos todos os elementos
           if indice_atual == num_elementos:
               resultados_finais.append(subconjunto_temporario.copy()) # Adiciona uma cópia
               return

           # Opção 1: Não incluir o elemento atual
           gerar_subconjuntos_recursivo(indice_atual + 1)

           # Opção 2: Incluir o elemento atual
           subconjunto_temporario.append(elementos[indice_atual])
           gerar_subconjuntos_recursivo(indice_atual + 1)
           subconjunto_temporario.pop() # Desfaz a escolha (restaura o estado)

       gerar_subconjuntos_recursivo(0)
       return resultados_finais

Por que .copy() e .pop() são Essenciais?

• subconjunto_temporario.copy(): Quando uma solução (um subconjunto completo) é encontrada e adicionada a resultados_finais, é crucial adicionar uma cópia do subconjunto_temporario. Se adicionarmos a lista diretamente (resultados_finais.append(subconjunto_temporario)), estaremos adicionando uma referência à mesma lista. Conforme subconjunto_temporario é modificado por chamadas recursivas subsequentes (via .pop() e .append()), todas as entradas em resultados_finais apontariam para a lista mutável e seriam alteradas, resultando em subconjuntos vazios ou incorretos.
• subconjunto_temporario.pop(): Após explorar todos os caminhos possíveis com o elementos[indice_atual] incluído, devemos removê-lo de subconjunto_temporario. Isso é chamado de "restaurar o estado". Garante que, ao retornar para o nível de recursão anterior, a lista subconjunto_temporario reflita corretamente as escolhas feitas até aquele ponto, permitindo que outros ramos da árvore de decisão sejam explorados sem interferências das escolhas feitas em um ramo já processado.

Abordagem 2: Enumerar Próximos Elementos

Nesta abordagem, em vez de decidir para cada elemento se ele está dentro ou fora, nós construímos os subconjuntos seelcionando elementos um por um e garantindo que cada elemento selecionado seja de um índice maior que o elemento selecionado anteriormente para evitar duplicatas.

Lógica de Backtracking

A cada passo recursivo, a nossa tarefa é construir um subconjunto a partir de uma posição inicial. Primeiro, adicionamos a configuração atual do nosso subconjunto_temporario aos resultados_finais (pois qualquer ponto na construção de um caminho é um subconjunto válido). Em seguida, iteramos pelos elementos restantes a partir do indice_inicio. Para cada elemento, nós o adicionamos ao subconjunto_temporario, fazemos uma chamada recursiva para continuar a construção a partir do próximo elemento, e depois o removemos (restaurando o estado) para que a iteração possa continuar com outros elementos na posição atual.

Exemplo de Código (Python)

class Solution:
   def todosSubconjuntos_alternativo(self, elementos: list[int]) -> list[list[int]]:
       num_elementos = len(elementos)
       if num_elementos == 0:
           return [[]] # O único subconjunto de um conjunto vazio é o próprio conjunto vazio

       resultados_finais = []
       subconjunto_temporario = []

       def explorar_subconjuntos_iterativo(indice_inicio: int):
           # Qualquer `subconjunto_temporario` no caminho é um subconjunto válido
           resultados_finais.append(subconjunto_temporario.copy())

           # Itera sobre os elementos restantes a partir de `indice_inicio`
           for j in range(indice_inicio, num_elementos):
               subconjunto_temporario.append(elementos[j]) # Faz a escolha
               explorar_subconjuntos_iterativo(j + 1)     # Chama recursivamente para os elementos subsequentes
               subconjunto_temporario.pop()               # Desfaz a escolha (restaura o estado)

       explorar_subconjuntos_iterativo(0) # Inicia a exploração a partir do primeiro elemento
       return resultados_finais

Partição de Palíndromos

Dada uma string s, o objetivo é particionar s de forma que cada substring da partição seja um palíndromo. Retorne todas as partições possíveis.

Lógica de Backtracking

Neste problema, o backtracking nos ajuda a encontrar todos os pontos de "corte" possíveis na string. Começamos no início da string. Para cada possível ponto de corte, verificamos se a substring resultante é um palíndromo. Se for, adicionamos essa substring à nossa partição atual e chamamos recursivamente a função para o restante da string. Se não for um palíndromo, essa ramificação é inválida. Quando a recursão atinge o final da string, uma partição válida foi encontrada.

Exemplo de Código (Python)

class Solution:
   def particionarPalindromos(self, s: str) -> list[list[str]]:
       num_caracteres = len(s)
       if num_caracteres == 0:
           return []

       particoes_validas = []
       particao_atual = [] # Armazena a partição sendo construída

       def encontrar_particoes_palindromicas(indice_inicio: int):
           # Condição base: se chegamos ao final da string, adicionamos a partição
           if indice_inicio == num_caracteres:
               particoes_validas.append(particao_atual.copy())
               return

           # Itera sobre possíveis pontos de término para a substring atual
           for indice_fim in range(indice_inicio, num_caracteres):
               # Extrai a substring
               substring_teste = s[indice_inicio : indice_fim + 1]
               
               # Verifica se a substring é um palíndromo
               if substring_teste == substring_teste[::-1]:
                   particao_atual.append(substring_teste) # Faz a escolha
                   # Chama recursivamente para o restante da string
                   encontrar_particoes_palindromicas(indice_fim + 1)
                   particao_atual.pop() # Desfaz a escolha (restaura o estado)

       encontrar_particoes_palindromicas(0) # Inicia a busca a partir do índice 0
       return particoes_validas