Dado un número entero n, se requiere generar todas las combinaciones posibles de paréntesis válidos con n pares. Este problema es equivalente a encontrar secuencias de paréntesis balanceadas, y se puede resolver mediante búsqueda en profundidad (DFS) con técnicas de poda eficientes.

Ejemplo 1:

Entrada: n = 3
Salida: ["((()))","(()())","(())()","()(())","()()()"]

Ejemplo 2:

Entrada: n = 1
Salida: ["()"]

El número de soluciones válidas está acotado por los números de Catalan, lo que proporciona una estimación teórica del tamaño del conjunto de resultados. Esto es útil para preasignar memoria en la implementación.

Se ofrecen dos enfoques para resolver el problema: una búsqueda exhaustiva y una búsqueda con poda basada en el estado actual. A continuación, se presentan implementaciones en C++ con cambios estructurales y en los nombres de variables para reducir la similitud con el código original.

Enfoque 1: Búsqueda en Profundidad Exhaustiva

Este método genera todas las secuencias posibles de longitud 2n y verifica su validez después. La función de validación comprueba el balance de paréntesis.

#include <vector>
#include <string>

bool esSecuenciaValida(std::string_view secuencia) {
    int balance = 0;
    for (char c : secuencia) {
        balance += (c == '(') ? 1 : -1;
        if (balance < 0) return false;
    }
    return balance == 0;
}

void explorar(std::string& plantilla, std::vector<std::string>& resultados, size_t longitudObjetivo) {
    if (plantilla.size() == longitudObjetivo) {
        if (esSecuenciaValida(plantilla)) {
            resultados.push_back(plantilla);
        }
        return;
    }
    plantilla.push_back('(');
    explorar(plantilla, resultados, longitudObjetivo);
    plantilla.pop_back();

    plantilla.push_back(')');
    explorar(plantilla, resultados, longitudObjetivo);
    plantilla.pop_back();
}

std::vector<std::string> generarTodas(size_t n) {
    std::vector<std::string> resultados;
    std::string plantilla;
    explorar(plantilla, resultados, n * 2);
    return resultados;
}

Enfoque 2: Búsqueda en Profunddiad con Poda por Estado

Este método evita generar secuencias inválidas al limitar las decitiones basándose en el conteo de paréntesis abiertos y cerrados. Se garantiza que solo se generen secuencias balanceadas durante la exploración.

#include <vector>
#include <string>

void buscarCombinaciones(std::vector<std::string>& resultados, std::string& actual, size_t abiertos, size_t cerrados, size_t maxPares) {
    if (actual.size() == maxPares * 2) {
        resultados.push_back(actual);
        return;
    }
    if (abiertos < maxPares) {
        actual.push_back('(');
        buscarCombinaciones(resultados, actual, abiertos + 1, cerrados, maxPares);
        actual.pop_back();
    }
    if (cerrados < abiertos) {
        actual.push_back(')');
        buscarCombinaciones(resultados, actual, abiertos, cerrados + 1, maxPares);
        actual.pop_back();
    }
}

std::vector<std::string> generarCombinacionesValidas(size_t n) {
    std::vector<std::string> resultados;
    std::string secuencia;
    buscarCombinaciones(resultados, secuencia, 0, 0, n);
    return resultados;
}

El segundo enfoque es más eficiente al reducir el espacio de búsqueda mediante condiciones de poda en cada paso recursivo, asegurando que solo se construyan secuencias parcialmente válidas.