A técnica de backtracking é uma estratégia algorítmica fundamental, frequentemente utilizada para resolver problemas de otimização e contagem que envolvem a construção incremental de soluções. Conceitualmente, cada busca em profundidade (DFS) pode ser visualizada como a travessia de uma árvore de estados, onde cada nó representa uma escolha parcial na solução. Uma condição de parada para a recursão geralmente ocorre quando uma variável de controle atinge um limite ou quando um estado final é alcançado.
O backtracking essencialmente expande uma busca em profundidade com a capacidade de "desfazer" a última escolha feita. Isso significa que, após explorar todos os caminhos possíveis a partir de uma escolha, o algoritmo reverte essa escolha para tentar outras alternativas. Em termos práticos, para estruturas de dados como vector ou deque, isso se traduz em um pop_back() após a chamada recursiva.
A necessidade de remover duplicatas é um fator importante. Existem duas abordagens principais:
- Com ordenação: Se a entrada puder ser ordenada, um array ou
std::vectorpode ser usado para rastrear elementos visitados, requerendopop_back()ou a redefinição de um estadoused(booleano) ao retroceder. - Sem ordenação (ou por camada): Se a ordenação não for viável, um
std::unordered_set(ou umstd::map, ou um array booleano para pequenos domínios de dados) pode ser usado para garantir unicidade em cada nível da recursão. É crucial inicializar o conjunto para cada nível para evitar que escolhas feitas em níveis anteriores afetem o nível atual, e geralmente não é necessário "apagar" elementos, pois um novo conjunto é usado para a próxima camada.
Alguns pontos cruciais a considerar na implementação de backtracking:
- Ponto de partida do loop
for: Para problemas de combinação (onde a ordem não importa), o loop geralmente começa a partir de umstartIndexpara evitar combinações repetidas. Para problemas de permutação (onde a ordem importa), o loop deve sempre começar do índice 0. - Reutilização de elementos: Se os elementos podem ser reutilizados na mesma combinação/permutação, o índice de partida para a próxima chamada recursiva é
i. Se cada elemento só pode ser usado uma vez, o índice éi + 1. - Registro de resultados: As soluções devem ser registradas em cada nó da árvore de recursão ou apenas nas folhas? Isso depende da definição do problema. Se o objetivo é coletar todos os subconjuntos, você registra em cada nó. Se o objetivo é encontrar permutações completas, você registra apenas nas folhas (quando a "profundidade" da recursão atinge o tamanho desejado).
- Retorno antecipado: Se apenas uma solução é necesária (como no Sudoku), a função recursiva pode retornar um
bool. Se uma chamada recursiva retornartrue, a função atual também pode retornartrue, encerrando a busca.
Combinações Simples
Problema: Gerar todas as combinações de k números a partir de n (1 a n).
class SolucaoCombinacoes {
private:
std::vector<std::vector<int>> todasCombinacoes; // Armazena todas as combinações válidas
std::vector<int> combinacaoAtual; // Armazena a combinação sendo construída
// Função recursiva de backtracking
void gerarCombinacoes(int valorMaximo, int tamanhoDesejado, int indiceInicial) {
// Condição de parada: a combinação atual atingiu o tamanho desejado
if (combinacaoAtual.size() == tamanhoDesejado) {
todasCombinacoes.push_back(combinacaoAtual);
return; // Importante retornar para não continuar a exploração desnecessariamente
}
// Iterar sobre os possíveis números a serem adicionados à combinação
// O loop começa de 'indiceInicial' para evitar duplicações e garantir ordem crescente
for (int i = indiceInicial; i <= valorMaximo; ++i) {
combinacaoAtual.push_back(i); // Adiciona o número atual
// Chamada recursiva para construir a próxima parte da combinação
// 'i + 1' garante que cada número é usado no máximo uma vez e mantém a combinação ordenada
gerarCombinacoes(valorMaximo, tamanhoDesejado, i + 1);
combinacaoAtual.pop_back(); // Remove o número (backtracking)
}
}
public:
std::vector<std::vector<int>> combine(int n, int k) {
todasCombinacoes.clear(); // Limpa resultados anteriores
combinacaoAtual.clear(); // Limpa caminho anterior
gerarCombinacoes(n, k, 1); // Inicia a busca a partir do número 1
return todasCombinacoes;
}
};
**Otimização (Poda):**Uma otimização comum para o problema de combinações é a poda (pruning), que reduz o número de chamadas recursivas. Se sabemos que os números restantes não são suficientes para formar uma combinação do tamanho desejado, podemos parar a busca.
void gerarCombinacoesOtimizada(int valorMaximo, int tamanhoDesejado, int indiceInicial) {
if (combinacaoAtual.size() == tamanhoDesejado) {
todasCombinacoes.push_back(combinacaoAtual);
return;
}
// Poda: valorMaximo - (tamanhoDesejado - combinacaoAtual.size()) + 1
// Isso significa que, se faltam 'tamanhoDesejado - combinacaoAtual.size()' elementos,
// o maior número que podemos escolher é 'valorMaximo - (tamanhoDesejado - combinacaoAtual.size())'.
// Adicionamos +1 porque o loop é inclusivo (<=).
for (int i = indiceInicial; i <= valorMaximo - (tamanhoDesejado - combinacaoAtual.size()) + 1; ++i) {
combinacaoAtual.push_back(i);
gerarCombinacoesOtimizada(valorMaximo, tamanhoDesejado, i + 1);
combinacaoAtual.pop_back();
}
}
Soma de Combinações III
Problema: Encontrar todas as combinações de k números que somam n, usando apenas números de 1 a 9, e onde cada combinação é única.
class SolucaoCombinacaoSomaIII {
private:
std::vector<std::vector<int>> resultadosFinais; // Armazena as combinações que atendem aos critérios
std::vector<int> caminhoAtual; // Combinação em construção
// Recursão com parâmetros para a soma alvo, número de elementos e soma acumulada
void encontrarSomas(int somaAlvo, int numElementos, int somaAcumulada, int inicioBusca) {
// Poda: Se a soma atual já exceder o alvo, não há necessidade de continuar
if (somaAcumulada > somaAlvo) {
return;
}
// Condição de parada: Se o caminho atual atingiu o número de elementos desejado
if (caminhoAtual.size() == numElementos) {
// Se a soma acumulada também é igual ao alvo, então é uma solução válida
if (somaAcumulada == somaAlvo) {
resultadosFinais.push_back(caminhoAtual);
}
return; // Retorna independentemente da soma, pois o tamanho está correto
}
// Iterar sobre os números de 'inicioBusca' até 9
// Poda adicional no loop: se 'i' for muito grande, não haverá números suficientes para atingir 'numElementos'
for (int i = inicioBusca; i <= 9 - (numElementos - caminhoAtual.size()) + 1; ++i) {
caminhoAtual.push_back(i); // Adiciona o número ao caminho
somaAcumulada += i; // Atualiza a soma
// Chamada recursiva, garantindo que o próximo número seja maior (i + 1)
encontrarSomas(somaAlvo, numElementos, somaAcumulada, i + 1);
somaAcumulada -= i; // Desfaz a soma (backtracking)
caminhoAtual.pop_back(); // Remove o número (backtracking)
}
}
public:
std::vector<std::vector<int>> combinationSum3(int k, int n) {
resultadosFinais.clear();
caminhoAtual.clear();
encontrarSomas(n, k, 0, 1); // Inicia a busca com soma 0 e a partir do número 1
return resultadosFinais;
}
};
Combinações de Letras de Telefone
Problema: Dada uma string contendo dígitos de 2 a 9, retornar todas as possíveis combinações de letras que os números podem representar.
class SolucaoLetrasTelefone {
private:
// Mapeamento de dígitos para letras correspondentes
const std::string mapeamentoDigitoLetras[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
std::vector<std::string> resultadosCombinacoes; // Armazena as combinações de letras
std::string construcaoAtual; // A combinação de letras sendo construída
// Função de backtracking principal
void gerarCombinacoesRecursivo(const std::string& digitosEntrada, int indiceDigito) {
// Condição de parada: se todos os dígitos foram processados
if (indiceDigito == digitosEntrada.size()) {
resultadosCombinacoes.push_back(construcaoAtual);
return;
}
// Converte o caractere do dígito para um inteiro
int digitoNumerico = digitosEntrada[indiceDigito] - '0';
// Obtém as letras correspondentes a este dígito
std::string letrasPossiveis = mapeamentoDigitoLetras[digitoNumerico];
// Itera sobre cada letra possível para o dígito atual
for (char letra : letrasPossiveis) {
construcaoAtual.push_back(letra); // Adiciona a letra ao caminho atual
// Chamada recursiva para processar o próximo dígito
gerarCombinacoesRecursivo(digitosEntrada, indiceDigito + 1);
construcaoAtual.pop_back(); // Remove a letra (backtracking)
}
}
public:
std::vector<std::string> letterCombinations(std::string digits) {
resultadosCombinacoes.clear();
construcaoAtual.clear();
if (digits.empty()) { // Caso de entrada vazia
return resultadosCombinacoes;
}
gerarCombinacoesRecursivo(digits, 0); // Inicia a recursão do primeiro dígito (índice 0)
return resultadosCombinacoes;
}
};
Soma de Combinações I (Com Repetição de Elementos)
Problema: Encontrar todas as combinações de candidates que somam target. Os mesmos números podem ser escolhidos um número ilimitado de vezes.
class SolucaoCombinacaoSoma {
private:
std::vector<std::vector<int>> conjuntoDeSomas;
std::vector<int> somaParcial;
// Função recursiva para encontrar combinações com repetição
void buscarSomas(std::vector<int>& candidatos, int valorAlvo, int somaAtual, int indicePartida) {
// Poda: Se a soma atual excede o valor alvo, este caminho não é válido
if (somaAtual > valorAlvo) {
return;
}
// Condição de parada: Se a soma atual é igual ao valor alvo, encontramos uma solução
if (somaAtual == valorAlvo) {
conjuntoDeSomas.push_back(somaParcial);
return;
}
// Iterar sobre os candidatos a partir de 'indicePartida'
for (int i = indicePartida; i < candidatos.size(); ++i) {
somaParcial.push_back(candidatos[i]); // Adiciona o candidato atual
somaAtual += candidatos[i]; // Atualiza a soma
// Chamada recursiva: 'i' em vez de 'i + 1' permite a reutilização do mesmo candidato
buscarSomas(candidatos, valorAlvo, somaAtual, i);
somaAtual -= candidatos[i]; // Desfaz a soma (backtracking)
somaParcial.pop_back(); // Remove o candidato (backtracking)
}
}
public:
std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
conjuntoDeSomas.clear();
somaParcial.clear();
buscarSomas(candidates, target, 0, 0); // Inicia a busca com soma 0 do primeiro candidato
return conjuntoDeSomas;
}
};
Soma de Combinações II (Sem Repetição, Com Duplicatas na Entrada)
Problema: Encontrar todas as combinações únicas de candidates que somam target, onde cada número em candidates só pode ser usado uma vez por combinação. candidates pode conter números duplicados.
class SolucaoCombinacaoSomaDuplicatas {
private:
std::vector<std::vector<int>> colecaoResultados;
std::vector<int> caminhoIntermediario;
// Função de backtracking para combinações sem repetição e com duplicatas
void explorarSomasUnicas(std::vector<int>& candidatos, int alvo, int somaAtual, int inicioBusca, std::vector<bool>& utilizados) {
// Condição de parada: Encontrou a soma alvo
if (somaAtual == alvo) {
colecaoResultados.push_back(caminhoIntermediario);
return;
}
// Poda: Se a soma atual excede o alvo, este caminho não é válido
if (somaAtual > alvo) {
return;
}
// Iterar sobre os candidatos, com otimização de poda no loop
for (int i = inicioBusca; i < candidatos.size() && somaAtual + candidatos[i] <= alvo; ++i) {
// Lógica para lidar com duplicatas no MESMO NÍVEL de recursão (para evitar combinações repetidas)
// Se o elemento atual é igual ao anterior E o anterior NÃO foi usado no ramo atual (ou seja, está no mesmo nível)
if (i > inicioBusca && candidatos[i] == candidatos[i - 1] && !utilizados[i - 1]) {
continue; // Pula este elemento para evitar duplicatas na saída
}
caminhoIntermediario.push_back(candidatos[i]); // Adiciona o candidato
somaAtual += candidatos[i]; // Atualiza a soma
utilizados[i] = true; // Marca como utilizado para este caminho
// Chamada recursiva: 'i + 1' porque cada número só pode ser usado uma vez
explorarSomasUnicas(candidatos, alvo, somaAtual, i + 1, utilizados);
utilizados[i] = false; // Desmarca (backtracking)
somaAtual -= candidatos[i]; // Desfaz a soma (backtracking)
caminhoIntermediario.pop_back(); // Remove o candidato (backtracking)
}
}
public:
std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
colecaoResultados.clear();
caminhoIntermediario.clear();
std::vector<bool> statusUtilizacao(candidates.size(), false); // Array para rastrear uso
std::sort(candidates.begin(), candidates.end()); // É essencial ordenar para lidar com duplicatas
explorarSomasUnicas(candidates, target, 0, 0, statusUtilizacao);
return colecaoResultados;
}
};
Particionamento de Palíndromos
Problema: Dada uma string s, particioná-la de forma que cada substring da partição seja um palíndromo. Retorne todas as possíveis partições.
class ParticionadorPalindromo {
private:
std::vector<std::vector<std::string>> todasParticoes;
std::vector<std::string> particaoAtual;
// Função auxiliar para verificar se uma substring é um palíndromo
bool ehPalindromo(const std::string& texto, int inicio, int fim) {
while (inicio < fim) {
if (texto[inicio] != texto[fim]) {
return false;
}
inicio++;
fim--;
}
return true;
}
// Função de backtracking para encontrar partições de palíndromos
void buscarParticoes(std::string& textoOriginal, int inicioSegmento) {
// Condição de parada: se 'inicioSegmento' alcançou ou ultrapassou o final da string
if (inicioSegmento >= textoOriginal.size()) {
todasParticoes.push_back(particaoAtual);
return;
}
// Iterar para encontrar todos os possíveis pontos de corte para o segmento atual
for (int i = inicioSegmento; i < textoOriginal.size(); ++i) {
// Verifica se a substring de 'inicioSegmento' até 'i' é um palíndromo
if (ehPalindromo(textoOriginal, inicioSegmento, i)) {
// Extrai a substring
std::string sub = textoOriginal.substr(inicioSegmento, i - inicioSegmento + 1);
particaoAtual.push_back(sub); // Adiciona ao caminho
// Chamada recursiva para a próxima parte da string, começando após o palíndromo atual
buscarParticoes(textoOriginal, i + 1);
particaoAtual.pop_back(); // Remove o palíndromo (backtracking)
}
}
}
public:
std::vector<std::vector<std::string>> partition(std::string s) {
todasParticoes.clear();
particaoAtual.clear();
if (s.empty()) {
return todasParticoes;
}
buscarParticoes(s, 0); // Inicia a busca do início da string
return todasParticoes;
}
};
Restauração de Endereços IP
Problema: Dada uma string contendo apenas dígitos, restaurar todos os possíveis endereços IP válidos.
class RestauradorEnderecosIP {
private:
std::vector<std::string> ipsValidos;
// Verifica se um segmento de string [inicio, fim] é um número IP válido (0-255, sem zeros à esquerda)
bool segmentoValido(const std::string& s, int inicio, int fim) {
if (inicio > fim) {
return false;
}
// Segmento '0x' ou '00' é inválido, a menos que seja apenas '0'
if (s[inicio] == '0' && inicio != fim) {
return false;
}
int valorNumerico = 0;
for (int i = inicio; i <= fim; ++i) {
if (s[i] < '0' || s[i] > '9') { // Caracteres não-numéricos
return false;
}
valorNumerico = valorNumerico * 10 + (s[i] - '0');
if (valorNumerico > 255) { // Valor excede 255
return false;
}
}
return true;
}
// Função de backtracking para construir endereços IP
void construirIP(std::string& strNumeros, int indiceAtual, int numPontosAdicionados) {
// Condição de parada: 3 pontos foram adicionados
if (numPontosAdicionados == 3) {
// Verifica se o último segmento é válido
if (segmentoValido(strNumeros, indiceAtual, strNumeros.size() - 1)) {
ipsValidos.push_back(strNumeros);
}
return;
}
// Itera para encontrar o próximo ponto
for (int i = indiceAtual; i < strNumeros.size(); ++i) {
// Verifica se o segmento atual [indiceAtual, i] é válido
if (segmentoValido(strNumeros, indiceAtual, i)) {
// Insere um ponto na posição i + 1
strNumeros.insert(strNumeros.begin() + i + 1, '.');
numPontosAdicionados++;
// Chamada recursiva para o próximo segmento (começando em i + 2, após o ponto)
construirIP(strNumeros, i + 2, numPontosAdicionados);
numPontosAdicionados--; // Backtracking: remove o ponto
strNumeros.erase(strNumeros.begin() + i + 1); // Remove o ponto
} else {
// Se o segmento atual não é válido, segmentos mais longos a partir de 'indiceAtual'
// também não serão válidos, então podemos parar neste nível.
break;
}
}
}
public:
std::vector<std::string> restoreIpAddresses(std::string s) {
ipsValidos.clear();
// Poda: um IP válido tem entre 4 e 12 dígitos (3 pontos + 4 segmentos de 1 a 3 dígitos)
if (s.size() > 12 || s.size() < 4) {
return ipsValidos;
}
construirIP(s, 0, 0); // Inicia a construção com 0 pontos e do índice 0
return ipsValidos;
}
};
Subconjuntos
Problema: Dada uma matriz de inteiros nums distintos, retorne todos os subconjuntos (conjunto de potência).
class GeradorSubconjuntos {
private:
std::vector<std::vector<int>> todosSubconjuntos;
std::vector<int> subconjuntoAtual;
// Função de backtracking para gerar subconjuntos
void gerar(std::vector<int>& numerosEntrada, int indiceInicio) {
// A cada chamada recursiva, o `subconjuntoAtual` representa um subconjunto válido
todosSubconjuntos.push_back(subconjuntoAtual);
// O loop itera pelos elementos restantes a partir de `indiceInicio`
for (int i = indiceInicio; i < numerosEntrada.size(); ++i) {
subconjuntoAtual.push_back(numerosEntrada[i]); // Adiciona o elemento
// Chamada recursiva para o próximo elemento, garantindo que o próximo
// elemento seja maior para evitar duplicatas em combinações
gerar(numerosEntrada, i + 1);
subconjuntoAtual.pop_back(); // Remove o elemento (backtracking)
}
// Condição de parada implícita: quando o loop `for` termina,
// significa que todos os elementos a partir de `indiceInicio` foram explorados.
}
public:
std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
todosSubconjuntos.clear();
subconjuntoAtual.clear();
gerar(nums, 0); // Inicia a geração a partir do índice 0
return todosSubconjuntos;
}
};
Subconjuntos II (Com Duplicatas)
Problema: Dada uma matriz de inteiros nums que podem conter duplicatas, retorne todos os subconjuntos únicos.
class GeradorSubconjuntosComDuplicatas {
private:
std::vector<std::vector<int>> resultadosSubconjuntos;
std::vector<int> caminhoConstruido;
// Função de backtracking para subconjuntos únicos com duplicatas na entrada
void explorarSubconjuntos(std::vector<int>& numeros, int indicePartida, std::vector<bool>& rastreados) {
resultadosSubconjuntos.push_back(caminhoConstruido); // Cada caminho é um subconjunto
for (int i = indicePartida; i < numeros.size(); ++i) {
// Lógica para lidar com duplicatas no MESMO NÍVEL de recursão
// Se o elemento atual é igual ao anterior E o anterior NÃO foi usado no ramo atual (mesmo nível)
if (i > 0 && numeros[i] == numeros[i - 1] && !rastreados[i - 1]) {
continue; // Pula este elemento
}
caminhoConstruido.push_back(numeros[i]); // Adiciona
rastreados[i] = true; // Marca como utilizado
explorarSubconjuntos(numeros, i + 1, rastreados); // Recursão
rastreados[i] = false; // Desmarca (backtracking)
caminhoConstruido.pop_back(); // Remove (backtracking)
}
}
public:
std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
resultadosSubconjuntos.clear();
caminhoConstruido.clear();
std::vector<bool> elementosUtilizados(nums.size(), false);
std::sort(nums.begin(), nums.end()); // Ordenar é crucial para lidar com duplicatas
explorarSubconjuntos(nums, 0, elementosUtilizados);
return resultadosSubconjuntos;
}
};
Sequências Crescentes
Problema: Dada uma matriz de inteiros, retornar todas as suas subsequências crescentes de comprimento pelo menos 2.
class SubsequenciasCrescentes {
private:
std::vector<std::vector<int>> colecaoSubsequencias;
std::vector<int> sequenciaAtual;
// Função de backtracking para encontrar subsequências crescentes
void encontrarSubsequencias(std::vector<int>& numeros, int indiceBusca) {
// Se a sequência atual tem pelo menos 2 elementos, é uma solução válida
if (sequenciaAtual.size() > 1) {
colecaoSubsequencias.push_back(sequenciaAtual);
// IMPORTANTE: Não retornar aqui, pois uma subsequência pode ser prefixo de outra
}
// Usar um unordered_set para evitar duplicatas NO MESMO NÍVEL de recursão
std::unordered_set<int> elementosJaUsadosNesteNivel;
for (int i = indiceBusca; i < numeros.size(); ++i) {
// Condição 1: A subsequência deve ser crescente
// Condição 2: O elemento não deve ter sido usado neste nível para evitar duplicatas
if ((!sequenciaAtual.empty() && numeros[i] < sequenciaAtual.back()) ||
(elementosJaUsadosNesteNivel.count(numeros[i]))) {
continue;
}
elementosJaUsadosNesteNivel.insert(numeros[i]); // Marca como usado neste nível
sequenciaAtual.push_back(numeros[i]); // Adiciona o elemento
encontrarSubsequencias(numeros, i + 1); // Chamada recursiva
sequenciaAtual.pop_back(); // Remove (backtracking)
}
}
public:
std::vector<std::vector<int>> findSubsequences(std::vector<int>& nums) {
colecaoSubsequencias.clear();
sequenciaAtual.clear();
encontrarSubsequencias(nums, 0);
return colecaoSubsequencias;
}
};
// Versão otimizada usando um array hash para controle de uso no nível
void encontrarSubsequenciasOtimizado(std::vector<int>& nums, int startIndex, std::vector<std::vector<int>>& result, std::vector<int>& path) {
if (path.size() > 1) {
result.push_back(path);
}
// Array para rastrear elementos usados neste nível, assumindo o range [-100, 100]
int contagemUsados[201] = {0}; // Mapeia [-100, 100] para [0, 200]
for (int i = startIndex; i < nums.size(); ++i) {
if ((!path.empty() && nums[i] < path.back()) || contagemUsados[nums[i] + 100] == 1) {
continue;
}
contagemUsados[nums[i] + 100] = 1; // Marca como usado neste nível
path.push_back(nums[i]);
encontrarSubsequenciasOtimizado(nums, i + 1, result, path);
path.pop_back();
}
}
Permutações
Problema: Dada uma matriz de inteiros nums distintos, retorne todas as permutações possíveis.
class GeradorPermutacoes {
private:
std::vector<std::vector<int>> todasAsPermutacoes;
std::vector<int> permutacaoEmConstrucao;
// Função de backtracking para gerar permutações
void construirPermutacoes(std::vector<int>& numerosBase, std::vector<bool>& statusUtilizacao) {
// Condição de parada: a permutação atual atingiu o tamanho total
if (permutacaoEmConstrucao.size() == numerosBase.size()) {
todasAsPermutacoes.push_back(permutacaoEmConstrucao);
return;
}
// Iterar sobre todos os números base para escolher o próximo elemento
for (int i = 0; i < numerosBase.size(); ++i) {
if (statusUtilizacao[i]) { // Se o número já foi usado, pular
continue;
}
statusUtilizacao[i] = true; // Marca como usado
permutacaoEmConstrucao.push_back(numerosBase[i]); // Adiciona à permutação
construirPermutacoes(numerosBase, statusUtilizacao); // Chamada recursiva
permutacaoEmConstrucao.pop_back(); // Remove (backtracking)
statusUtilizacao[i] = false; // Desmarca (backtracking)
}
}
public:
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
todasAsPermutacoes.clear();
permutacaoEmConstrucao.clear();
std::vector<bool> elementosUsados(nums.size(), false); // Rastreador de uso
construirPermutacoes(nums, elementosUsados);
return todasAsPermutacoes;
}
};
Permutações II (Com Duplicatas)
Problema: Dada uma matriz de inteiros nums que podem conter duplicatas, retorne todas as permutações únicas.
class GeradorPermutacoesComDuplicatas {
private:
std::vector<std::vector<int>> resultadosPermutacoes;
std::vector<int> caminhoAtualPermutacao;
void gerarPermutacoesUnicas(std::vector<int>& numeros, std::vector<bool>& elementosMarcados) {
if (caminhoAtualPermutacao.size() == numeros.size()) {
resultadosPermutacoes.push_back(caminhoAtualPermutacao);
return;
}
for (int i = 0; i < numeros.size(); ++i) {
// Condição para pular duplicatas NO MESMO NÍVEL de recursão
// Se o elemento já foi usado OU
// Se o elemento atual é igual ao anterior E o anterior NÃO foi usado no ramo atual (mesmo nível)
if (elementosMarcados[i] || (i > 0 && numeros[i] == numeros[i - 1] && !elementosMarcados[i - 1])) {
continue;
}
elementosMarcados[i] = true;
caminhoAtualPermutacao.push_back(numeros[i]);
gerarPermutacoesUnicas(numeros, elementosMarcados);
caminhoAtualPermutacao.pop_back();
elementosMarcados[i] = false;
}
}
public:
std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
resultadosPermutacoes.clear();
caminhoAtualPermutacao.clear();
std::vector<bool> estadoDeUso(nums.size(), false);
std::sort(nums.begin(), nums.end()); // Ordenar é essencial para lidar com duplicatas
gerarPermutacoesUnicas(nums, estadoDeUso);
return resultadosPermutacoes;
}
};
Reorganizar Roteiro de Voos
Problema: Dados uma lista de passagens aéreas, reconstrua o itinerário de voos a partir de "JFK" com a menor ordem lexicográfica.
class ItinerarioDeVoos {
private:
// Mapeia aeroporto de origem para um map de aeroporto de destino e suas contagens
// Usamos std::map para garantir que os destinos são ordenados lexicograficamente
std::unordered_map<std::string, std::map<std::string, int>> rotasDisponiveis;
std::vector<std::string> itinerarioFinal; // O itinerário reconstruído
// Função de backtracking. Retorna 'true' se um itinerário completo for encontrado.
bool buscarItinerario(int totalVoos, std::vector<std::string>& itinerarioAtual) {
// Condição de parada: Se o itinerário atual tem 'totalVoos + 1' aeroportos (totalVoos arestas)
if (itinerarioAtual.size() == totalVoos + 1) {
itinerarioFinal = itinerarioAtual; // Armazena este itinerário como o final (primeiro encontrado lexicograficamente)
return true; // Encontrou uma solução
}
// Obtém o último aeroporto adicionado ao itinerário
std::string aeroportoAtual = itinerarioAtual.back();
// Itera sobre os destinos possíveis a partir do 'aeroportoAtual'
// 'target' é um par (destino, contagem de voos para este destino)
for (auto& rota : rotasDisponiveis[aeroportoAtual]) {
if (rota.second > 0) { // Se ainda há voos disponíveis para este destino
itinerarioAtual.push_back(rota.first); // Adiciona o destino ao itinerário
rota.second--; // Diminui a contagem de voos
// Chamada recursiva: Se encontrar uma solução completa, propaga 'true'
if (buscarItinerario(totalVoos, itinerarioAtual)) {
return true;
}
itinerarioAtual.pop_back(); // Backtracking: remove o destino
rota.second++; // Backtracking: restaura a contagem de voos
}
}
return false; // Nenhum caminho válido a partir deste ponto
}
public:
std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
rotasDisponiveis.clear();
itinerarioFinal.clear();
// Constrói o mapa de rotas a partir das passagens
for (const auto& voo : tickets) {
rotasDisponiveis[voo[0]][voo[1]]++; // Incrementa a contagem de voos
}
itinerarioFinal.push_back("JFK"); // Começa sempre de "JFK"
buscarItinerario(tickets.size(), itinerarioFinal); // totalVoos é o número de passagens
return itinerarioFinal;
}
};
N-Rainhas
Problema: Colocar n rainhas em um tabuleiro de xadrez n x n de forma que nenhuma rainha ataque a outra.
class NRainhasSolucionador {
private:
std::vector<std::vector<std::string>> todasAsSolucoes;
// Função auxiliar para verificar se é seguro colocar uma rainha em (linha, coluna)
bool posicaoValida(int linha, int coluna, const std::vector<std::string>& tabuleiro, int dimensoes) {
// Verifica a coluna acima da posição atual
for (int i = 0; i < linha; ++i) {
if (tabuleiro[i][coluna] == 'Q') {
return false;
}
}
// Verifica a diagonal superior esquerda (45 graus)
for (int i = linha - 1, j = coluna - 1; i >= 0 && j >= 0; --i, --j) {
if (tabuleiro[i][j] == 'Q') {
return false;
}
}
// Verifica a diagonal superior direita (135 graus)
for (int i = linha - 1, j = coluna + 1; i >= 0 && j < dimensoes; --i, ++j) {
if (tabuleiro[i][j] == 'Q') {
return false;
}
}
return true;
}
// Função de backtracking para encontrar soluções para o problema N-Rainhas
void colocarRainhas(int dimensoes, int linhaAtual, std::vector<std::string>& tabuleiro) {
// Condição de parada: se todas as rainhas foram colocadas (linhaAtual atingiu 'dimensoes')
if (linhaAtual == dimensoes) {
todasAsSolucoes.push_back(tabuleiro);
return;
}
// Itera sobre cada coluna na 'linhaAtual' para tentar colocar uma rainha
for (int coluna = 0; coluna < dimensoes; ++coluna) {
// Se a posição (linhaAtual, coluna) é segura
if (posicaoValida(linhaAtual, coluna, tabuleiro, dimensoes)) {
tabuleiro[linhaAtual][coluna] = 'Q'; // Coloca a rainha
colocarRainhas(dimensoes, linhaAtual + 1, tabuleiro); // Recursão para a próxima linha
tabuleiro[linhaAtual][coluna] = '.'; // Backtracking: remove a rainha
}
}
}
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
todasAsSolucoes.clear();
// Inicializa um tabuleiro vazio com '.'
std::vector<std::string> tabuleiroInicial(n, std::string(n, '.'));
colocarRainhas(n, 0, tabuleiroInicial); // Inicia da primeira linha (índice 0)
return todasAsSolucoes;
}
};
Solucionador de Sudoku
Problema: Resolver um tabuleiro de Sudoku parcialmente preenchido.
class SolucionadorSudoku {
private:
// Verifica se é válido colocar 'valor' na posição (linha, coluna)
bool verificarValidade(int linha, int coluna, char valor, const std::vector<std::vector<char>>& tabuleiro) {
// Verifica a linha
for (int c = 0; c < 9; ++c) {
if (tabuleiro[linha][c] == valor) {
return false;
}
}
// Verifica a coluna
for (int r = 0; r < 9; ++r) {
if (tabuleiro[r][coluna] == valor) {
return false;
}
}
// Verifica o bloco 3x3
int inicioLinhaBloco = (linha / 3) * 3;
int inicioColunaBloco = (coluna / 3) * 3;
for (int r = inicioLinhaBloco; r < inicioLinhaBloco + 3; ++r) {
for (int c = inicioColunaBloco; c < inicioColunaBloco + 3; ++c) {
if (tabuleiro[r][c] == valor) {
return false;
}
}
}
return true;
}
// Função de backtracking principal para resolver o Sudoku
bool resolver(std::vector<std::vector<char>>& tabuleiroSudoku) {
// Iterar por cada célula do tabuleiro
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (tabuleiroSudoku[i][j] == '.') { // Se a célula está vazia
// Tenta colocar dígitos de '1' a '9'
for (char num = '1'; num <= '9'; ++num) {
if (verificarValidade(i, j, num, tabuleiroSudoku)) {
tabuleiroSudoku[i][j] = num; // Coloca o número
// Chamada recursiva para a próxima célula vazia
if (resolver(tabuleiroSudoku)) {
return true; // Se a recursão encontrar uma solução, propaga 'true'
}
tabuleiroSudoku[i][j] = '.'; // Backtracking: remove o número
}
}
return false; // Se nenhum número de 1 a 9 funciona para esta célula, o caminho é inválido
}
}
}
return true; // Se todos os loops terminam sem retornar 'false', o tabuleiro foi resolvido
}
public:
void solveSudoku(std::vector<std::vector<char>>& board) {
resolver(board);
}
};