Difícil · backtracking

Generar paréntesis

Ya escribiste un backtracker — Todas las permutaciones elegía entre n valores y deshacía su elección. Este elige entre dos caracteres exactamente, pero los dos contadores que guardan cada rama (open < n, close < open) hacen la poda que antes hacía el array used[].

En una fraseRecursión sobre posiciones: coloca <code>'('</code> si <code>open < n</code>, coloca <code>')'</code> si <code>close < open</code>; en la posición 2n, escribe. Probar '(' primero regala el orden lexicográfico.

El problema

Entrada: Un entero n (1 ≤ n ≤ 8).

Salida: Todas las cadenas válidas de n pares, una por línea, en el orden que produce probar '(' antes que ')' (lexicográfico).

Ejemplos:

Entrada	Salida
`2`	`(()) ()()`
`1`	`()`

Con n = 3 hay 5 cadenas válidas entre 2^6 = 64 combinaciones en bruto — las dos reglas de contadores descartan las otras 59 sin llegar a construirlas. Eso es podar: rechazar una rama antes de recorrerla.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — La validez son dos reglas locales

Un prefijo puede crecer hasta ser válido exactamente cuando (1) ha usado menos de n aperturas y (2) cada ')' que contiene está emparejada — lo que se reduce a close < open en cada paso. Dos contadores enteros cargan ambos hechos; sin pila y sin pasada de validación al final. Las reglas se comprueban al andar, y por eso el árbol se poda solo.

Pista 2 — El caso base escribe el buffer

Cuando pos == 2 * n el buffer contiene una cadena completa — y es válida por construcción, porque los contadores nunca permitieron otra cosa. Escríbela con salto de línea y vuelve. Fíjate en que no hay paso de validación alguno: la corrección vino de las reglas de ramificación, no de un chequeo.

Pista 3 — El orden de los dos intentos = el orden de salida

Dentro de la función, prueba '(' primero y ')' después. La profundidad-primero con ese orden visita las cadenas exactamente en orden lexicográfico — el mismo almuerzo gratis que en Todas las permutaciones. Intercambia las dos ramas y cada línea de tu salida se reordena.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < open) {
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}

Este es el backtracking con poda en su forma más pura: el espacio bruto es 2^(2n), los contadores lo recortan al número de Catalán — unos 4^n / n^1.5 — sin recorrer una sola rama desperdiciada. La familia crece: elegir de un conjunto en Todas las permutaciones, elegir bajo restricciones aquí. Parientes siguientes: subconjuntos con condición de suma, N-reinas, sudoku.

Análisis profundo

Por qué funciona

Dos contadores codifican todo el predicado de validez: menos de n aperturas usadas, y nunca más cierres que aperturas. Ramificar bajo esas guardas hace que cada hoja del árbol sea válida por construcción — sin validación posterior, y el árbol se poda antes de recorrerlo (las 2^(2n) cadenas en bruto colapsan al número de Catalán).

El coste

O(Catalán(n) × n) de tiempo — unos 4^n / n^1.5 cadenas, cada una escrita en O(n) — y O(n) de profundidad de recursión. Con n = 8 son 1430 cadenas; las 2^(2n) = 65536 en bruto solo se probarían si validaras al final en vez de podar al andar.

Dónde falla

Aflojar close < open a close < n escribe cadenas inválidas — la guarda es todo el algoritmo.
Olvidar escribir en pos == 2n (o escribir dentro de las ramas) produce prefijos parciales o duplicados.
Probar ')' primero reordena la salida; el juez compara secuencias, así que el orden de intento importa tanto como la validez.

Siguiente paso

Mismo esqueleto, reglas más ricas: elegir de un conjunto en Todas las permutaciones, elegir bajo dos contadores aquí. Ramas siguientes naturales: subconjuntos con suma objetivo, N-reinas.

Dos cosas para recordar

Podar = rechazar una rama antes de recorrerla; aquí bastan dos contadores.
El orden de intento del DFS define el orden de salida — '(' antes de ')' da lexicográfico gratis.

🐞 Esta versión falla: ábrela y pruébala

Comprueba close < n en vez de close < open — se cuelan cadenas inválidas

#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < n) {   // bug: should be close < open
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}