39. Combinational Sum: Combinaciones que suman a un objetivo (mediano)

Dado un arreglo de enteros únicos candidatos y un objetivo numérico objetivo, busca todas las combinaciones diferentes que sumen objetivo. Cada elemento puede usarse múltiples veces. Si se varía la cantidad de algún elemento, se considera una combinación distinta.

Entrada: candidatos = [2,3,6,7], objetivo = 7
Salida: [[2,2,3],[7]]

Entrada: candidatos = [2,3,5], objetivo = 8
Salida: [[2,2,2,2],[2,3,3],[3,5]]

Entrada: candidatos = [2], objetivo = 1
Salida: []

Restricciones:

• Longitud entre 1 y 30
• Elementos entre 2 y 40
• Objetivo entre 1 y 40

Solución usando backtracking:

class Solucion {
public:
    vector<vector<int>> resultados;
    vector<int> actual;
    void buscar(vector<int>& candidatos, int objetivo, int suma_actual, int inicio) {
        if (suma_actual == objetivo) {
            resultados.push_back(actual);
            return;
        }
        for (int k = inicio; k < candidatos.size() && suma_actual + candidatos[k] <= objetivo; ++k) {
            suma_actual += candidatos[k];
            actual.push_back(candidatos[k]);
            buscar(candidatos, objetivo, suma_actual, k);
            actual.pop_back();
            suma_actual -= candidatos[k];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidatos, int objetivo) {
        sort(candidatos.begin(), candidatos.end());
        buscar(candidatos, objetivo, 0, 0);
        return resultados;
    }
};

40. Combinational Sum II: Combinaciones únicas con un solo uso (mediano)

Dado un arreglo de enteros con posibles duplicados, encuentra todas las combincaiones que sumen objetivo. Cada elemento solo puede usarse una vez por combinación y el resultado no debe contener duplicados.

Entrada: candidatos = [10,1,2,7,6,1,5], objetivo = 8,
Salida: [[1,1,6],[1,2,5],[1,7],[2,6]]

Solución optimizada:

class Solucion {
public:
    vector<vector<int>> resultados;
    vector<int> camino;
    void procesar(vector<int>& candidatos, int objetivo, int suma, int inicio) {
        if(suma == objetivo) {
            resultados.push_back(camino);
            return;
        }
        for(int j = inicio; j < candidatos.size() && suma + candidatos[j] <= objetivo; ++j){
            if (j > inicio && candidatos[j] == candidatos[j - 1]) continue;
            camino.push_back(candidatos[j]);
            procesar(candidatos, objetivo, suma + candidatos[j], j + 1);
            camino.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidatos, int objetivo) {
        sort(candidatos.begin(), candidatos.end());
        procesar(candidatos, objetivo, 0, 0);
        return resultados;
    }
};

131. Partition Palindrome: Separación en subcadenas palíndromas (mediano)

Dada una cadena s, divídela en subcadenas palíndromas. Retorna todas las formas posibles de hacerlo.

Entrada: s = "aab"
Salida: [["a","a","b"],["aa","b"]]

Implementación:

class Particion {
public:
    vector<vector<string>> resultados;
    vector<string> partes;
    void dividir(const string& s, int inicio) {
        if(inicio >= s.size()) {
            resultados.push_back(partes);
            return;
        }
        for(int m = inicio; m < s.size(); ++m) {
            if(esPalindromo(s, inicio, m)) {
                partes.push_back(s.substr(inicio, m - inicio + 1));
                dividir(s, m + 1);
                partes.pop_back();
            }
        } 
    }
    bool esPalindromo(const string& s, int inicio, int fin) {
        while(inicio < fin) {
            if(s[inicio++] != s[fin--]) return false;
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        dividir(s, 0);
        return resultados;
    }
};