Teoría del Algoritmo de Retroceso

El retroceso es una técnica de búsqueda exhaustiva que explora sistemáticamente soluciones candidatas. Su impelmentación se basa en recursión, donde cada decisión genera un nuevo estado que se evalúa hasta alcanzar una solución o agotar las posibilidades.

• Casos de aplicación:
  • Problemas combinatorios: Selección de k elementos de un conjunto
  • Segmentación de cadenas: Divisiones válidas según reglas
  • Subconjuntos: Identificación de grupos que cumplen condiciones
  • Permutaciones: Generación de ordenamientos válidos
  • Problemas de tablero: Soluciones para N-Reinas o Sudoku

Estructura Básica

void busqueda(parámetros) {
    if (condición_terminación) {
        almacenar_solución;
        return;
    }
    
    for (elemento : elementos_disponibles) {
        procesar_elemento(elemento);
        busqueda(nuevos_parámetros); // Llamada recursiva
        revertir_proceso(elemento); // Retroceso
    }
}

77. Generación de Combinaciones

Dado un rango [1, n] y un tamaño k, generar todas las combinaciones únicas de k elementos.

Enfoque

• Iniciar búsqueda desde posición actual
• Almacenra combinación válida al alcanzar tamaño k
• Optimizar limitando búsqueda a elementos restantes suficientes

class Solucion {
public:
    vector<vector<int>> combinaciones;
    vector<int> actual;
    
    void buscar(int n, int k, int inicio) {
        if (actual.size() == k) {
            combinaciones.push_back(actual);
            return;
        }
        
        int limite = n - (k - actual.size()) + 1;
        for (int num = inicio; num <= limite; num++) {
            actual.push_back(num);
            buscar(n, k, num + 1);
            actual.pop_back();
        }
    }
    
    vector<vector<int>> combinar(int n, int k) {
        buscar(n, k, 1);
        return combinaciones;
    }
};

216. Combinaciones con Suma Específica

Encontrar todas las combinaciones de k dígitos distintos (1-9) cuya suma sea igual a n.

Optimizaciones

• Abandonar búsqueda si suma excede objetivo
• Limitar búsqueda a números restantes necesarios
• Validar combinación al alcanzar tamaño k

class CalculadorCombinaciones {
public:
    vector<vector<int>> resultados;
    vector<int> temporal;
    
    void calcular(int k, int objetivo, int inicio, int acumulado) {
        if (acumulado > objetivo) return;
        if (temporal.size() == k) {
            if (acumulado == objetivo) 
                resultados.push_back(temporal);
            return;
        }
        
        int limite = 9 - (k - temporal.size()) + 1;
        for (int num = inicio; num <= limite; num++) {
            temporal.push_back(num);
            calcular(k, objetivo, num + 1, acumulado + num);
            temporal.pop_back();
        }
    }
    
    vector<vector<int>> combinacionSuma(int k, int n) {
        calcular(k, n, 1, 0);
        return resultados;
    }
};

17. Combinaciones de Letras en Teléfono

Generar todas las combinaciones de letras representadas por dígitos telefónicos.

Mapeo de dígitos

const string teclas[10] = {
    "", "", "abc", "def", "ghi", 
    "jkl", "mno", "pqrs", "tuv", "wxyz"
};

Algoritmo

• Convertir dígito a índice numérico
• Explorar recursivamente cada letra correspondiente
• Al cmopletar dígitos, guardar combinación

class GeneradorLetras {
public:
    vector<string> salida;
    string cadena;
    
    void generarCombinaciones(string digitos, int indice) {
        if (indice == digitos.size()) {
            salida.push_back(cadena);
            return;
        }
        
        int digito = digitos[indice] - '0';
        string letras = teclas[digito];
        for (char letra : letras) {
            cadena += letra;
            generarCombinaciones(digitos, indice + 1);
            cadena.pop_back();
        }
    }
    
    vector<string> combinacionesTelefonicas(string digitos) {
        if (digitos.empty()) return {};
        generarCombinaciones(digitos, 0);
        return salida;
    }
};