216. Combinações Soma III

O objetivo deste problema é encontrar todas as combinações de k números distintos que, quando somados, resultam em n. As restrições especificam que apenas os dígitos de 1 a 9 podem ser utilizados e cada dígote pode ser usado no máximo uma vez.

A estratégia principal reside na utilização do algoritmo de backtracking. Podemos visualizar o processo de seleção como uma árvore N-ária, onde a profundidade da árvore corresponde ao número de elementos a serem selecionados (k) e a largura representa o conjunto de números disponíveis (1 a 9).

Para evitar combinações duplicadas (como [1, 2] e [2, 1]), é crucial controlar o ponto de partida da iteração em cada nível da recursão. A cada passo, iniciamos a busca a partir do número sgeuinte ao último selecionado.

Abaixo, apresentamos uma implementação em C++ que utiliza um vetor temporário para armazenar o caminho atual e uma variável para rastrear a soma acumulada:

class Solution {
private:
    vector<vector>> resultados;
    vector<int> caminho;

    void buscar(int k, int n, int somaAtual, int inicio) {
        if (caminho.size() == k) {
            if (somaAtual == n) {
                resultados.push_back(caminho);
            }
            return;
        }

        for (int i = inicio; i <= 9; i++) {
            caminho.push_back(i);
            buscar(k, n, somaAtual + i, i + 1);
            caminho.pop_back();
        }
    }

public:
    vector<vector>> combinationSum3(int k, int n) {
        buscar(k, n, 0, 1);
        return resultados;
    }
};
</vector></int></vector>

Otimização com Poda

A eficiência do algoritmo pode ser melhorada significativamente através de poda. Podemos interromper a recursão antecipadamente em dois cenários:

• Se a soma acumulada já exceder n, não há necessidade de continuar a busca neste ramo.
• O intervalo do loop pode ser ajustado. Se ainda precisamos de k - caminho.size() elementos, não faz sentido iterar até 9 se não houver números suficientes restantes para completar a combinação. O limite superior do loop torna-se 9 - (k - caminho.size()) + 1.

class Solution {
private:
    vector<vector>> resultados;
    vector<int> caminho;

    void buscarOtimizado(int k, int n, int somaAtual, int inicio) {
        if (somaAtual > n) return; // Poda por soma
        if (caminho.size() == k) {
            if (somaAtual == n) resultados.push_back(caminho);
            return;
        }

        // Poda no intervalo de iteração
        for (int i = inicio; i <= 9 - (k - caminho.size()) + 1; i++) {
            caminho.push_back(i);
            buscarOtimizado(k, n, somaAtual + i, i + 1);
            caminho.pop_back();
        }
    }

public:
    vector<vector>> combinationSum3(int k, int n) {
        buscarOtimizado(k, n, 0, 1);
        return resultados;
    }
};
</vector></int></vector>

17. Combinações de Letras de Números de Telefone

Dado uma string contendo dígitos de 2 a 9, o desafio consiste em retornar todas as possíveis combinações de letras que esses números poderiam representar, seguindo o mapeamento tradicional de um teclado de telefone.

A estrutura do mapeamento é fixa (2: "abc", 3: "def", etc.). A profundidade da recursão, neste caso, é determinada pelo comprimento da string de entrada, e os nós folha da árvore de recursão representam as combinações finais a serem retornadas.

O processo envolve três etapas lógicas:

1. Mapeamento: Utilizar um array ou mapa para associar cada dígito à sua string de letras correspondente.
2. Recursão: Para cada nível de profundidade (índice do dígito na string de entrada), iterar sobre todas as letras possíveis correspondentes àquele dígito, concatenando-as à combinação atual.
3. Condição de Parada: Quando o índice atual iguala o tamanho da string de entrada, a combinação está completa e deve ser armazenada.

class Solution {
private:
    const string mapa[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> saida;
    string combinacao;

    void dfs(const string& digitos, int idx) {
        if (idx == digitos.size()) {
            saida.push_back(combinacao);
            return;
        }

        int digito = digitos[idx] - '0';
        string letras = mapa[digito];

        for (char c : letras) {
            combinacao.push_back(c);
            dfs(digitos, idx + 1);
            combinacao.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        dfs(digits, 0);
        return saida;
    }
};
</string></string>

A complexidade de tempo é exponencial em relação ao tamanho da entrada, especificamente O(3^m * 4^n), onde m é a quantidade de dígitos que mapeiam para 3 letras e n a quantidade que mapeia para 4 letras.