Generate Parentheses

Q: ¿Cuál es la complejidad temporal de Generate Parentheses?

La solución con retroceso genera el número catalán C(n) = (2n)! / ((n+1)! n!) de cadenas, que crece como 4^n / (n^1.5 √π) . Cada cadena tiene una longitud de 2n y la búsqueda nunca desperdicia una rama, por lo que el tiempo total es O(4^n / √n) . El espacio adicional es O(n) para la cadena actual y la pila de llamadas, además de la salida.

Q: ¿Cuántas cadenas de paréntesis válidas hay para n pares?

Exactamente el enésimo número de Catalan: 1, 2, 5, 14, 42, 132, 429 y 1,430 para n de 1 a 8. Una forma de verlo: toda cadena bien formada es ( + A + ) + B, donde el primer ( se empareja con ese ) , y A y B están bien formadas con n-1 pares entre ellas. Al sumar según el tamaño de A, se obtiene la recurrencia de Catalan.

Q: ¿Por qué cerrado < abierto garantiza una cadena válida?

Una cadena falla exactamente cuando llega un ) sin que haya antes un ( sin emparejar, es decir, cuando la cantidad de ) superaría la cantidad de ( . Permitir ) solo mientras closed < opened evita que eso ocurra, y permitir ( solo mientras opened < n hace que ambas cantidades lleguen a n con una longitud de 2n . Juntas, las dos reglas describen cada prefijo de una cadena bien formada.

Q: ¿Se puede resolver Generate Parentheses sin recursión?

Sí. Mantén una pila de estados parciales, cada uno como una cadena con sus dos contadores, y amplía un estado con las mismas dos reglas. Si apilas la extensión ) antes que la extensión ( , primero se desapila la de ( y la salida permanece ordenada. El trabajo es el mismo; la gestión pasa de la pila de llamadas a tu propia pila.

MedioBacktracking Recursión

+10

Una cadena de paréntesis está bien formada cuando, al leerla de izquierda a derecha, el número de ) nunca supera el número de (, y ambos recuentos son iguales al final. Así, (())() está bien formada, mientras que ())( no lo está: su tercer carácter cierra un par que nunca se abrió.

Recibes un entero n. Devuelve todas las cadenas bien formadas compuestas por n paréntesis de apertura y n paréntesis de cierre, ordenadas lexicográficamente, donde ( va antes que ).

Función

generateParenthesis(n: integer) → string-array

ninteger: el número de pares de paréntesis
Devuelvestring-array: cada cadena bien formada de n pares, en orden lexicográfico

Restricciones

1 ≤ n ≤ 8
Para n = 8, la respuesta contiene 1,430 cadenas.

Ejemplos

Entrada: n = 3
Salida: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explicación: Tres pares se pueden ordenar de cinco maneras bien formadas. ((())) abre los tres antes de cerrar cualquiera y, como ( se ordena primero, encabeza la lista; ()()() cierra cada par de inmediato y aparece al final.

Entrada: n = 1
Salida: ["()"]
Explicación: Un par tiene una única disposición bien formada. La única otra cadena con un ( y un ) es )(, que se cierra antes de que haya nada abierto.

+10 pruebas ocultas al enviar

Para ir más allá

¿Puedes contar las cadenas bien formadas para n pares sin generarlas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Solo una pequeña proporción de las cadenas de longitud 2n está bien formada: 5 de las 64 cadenas para n = 3, y 1.430 de 65.536 para n = 8. La idea clave consiste en construir la cadena de izquierda a derecha y añadir únicamente caracteres que la mantengan válida, de modo que la búsqueda nunca explore una rama que no pueda completarse. Dos contadores determinan qué está permitido: cuántos ( has colocado y cuántos ). Probar ( antes que ) en cada paso hace que las cadenas ya salgan ordenadas.

Construye cada cadena y luego compruébala

Intuición

La forma directa consiste en llenar las 2n posiciones de todas las maneras posibles y conservar las cadenas que estén bien formadas. Cada posición contiene ( o ), así que hay 2^(2n) = 4^n cadenas. Una función recursiva coloca ( en la siguiente posición, vuelve a llamarse recursivamente, después coloca ) allí y vuelve a llamarse recursivamente; cada cadena completa pasa por una comprobación.

La comprobación recorre la cadena llevando un saldo: suma 1 por cada ( y resta 1 por cada ). La cadena está bien formada cuando el saldo nunca baja de 0 y termina en 0. Bajar de 0 significa que hay un ) sin ningún paréntesis abierto que cerrar, como en el tercer carácter de ())(.

Probar ( antes que ) en cada posición enumera las cadenas en orden lexicográfico, porque ( va antes que ). Así que las cadenas conservadas ya están ordenadas.

El coste es de 4^n cadenas, cada una comprobada en O(n). Para n = 8, eso equivale a 65,536 cadenas para 1,430 respuestas, así que se desperdicia alrededor del 98% del trabajo. Aquí termina porque n es como máximo 8, pero la cantidad se cuadruplica con cada par adicional, y sigue construyendo cadenas que empiezan con ), aunque el primer carácter ya las descarta.

Algoritmo

Mantén un búfer de 2n caracteres y una lista para las respuestas.
Escribe fill(pos). Si pos es igual a 2n, comprueba el búfer y guárdalo si está bien formado.
De lo contrario, coloca ( en pos y llama a fill(pos + 1); después coloca ) ahí y vuelve a llamarla.
Para comprobar una cadena, suma 1 por cada ( y resta 1 por cada ). Recházala en cuanto el balance sea menor que 0 o si no termina en 0.
Llama a fill(0) y devuelve las cadenas guardadas, ya ordenadas.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Retrocede en los recuentos de apertura y cierre

Intuición

Traslada la comprobación a la construcción. Un prefijo aún puede convertirse en una cadena bien formada exactamente cuando se cumplen dos reglas: usa como máximo n paréntesis de apertura y nunca tiene más ) que (. Así, en cada paso puedes añadir ( mientras opened < n, y ) mientras closed < opened. Cuando la cadena alcanza la longitud 2n, ambos recuentos son n y la cadena está bien formada, sin que quede nada por comprobar.

Este es el árbol completo para n = 2. Desde la cadena vacía solo se permite (, ya que todavía no hay nada abierto. Desde ( se permiten ambos. En la rama ((, opened ya es 2, así que solo cabe ), dos veces, lo que da (()). En la rama (), no hay nada abierto, así que solo cabe (, y después ), lo que da ()(). Cada rama termina en una respuesta: la búsqueda nunca construye una cadena que luego tenga que descartar.

No se omite ninguna respuesta. Cada prefijo de una cadena bien formada cumple ambas reglas, así que la búsqueda nunca rechaza el siguiente carácter que esa cadena necesita, y cada cadena se produce una sola vez, ya que sus caracteres trazan un único camino a través del árbol. El orden funciona como en el primer enfoque: dos cadenas difieren por primera vez en el punto donde se bifurcan sus caminos, y allí se explora primero la rama (.

cada hoja es una respuesta, y el número de respuestas para n pares es el número de Catalan C(n), que crece como 4^n / (n^1.5 √π). Cada nodo interno está en el camino hacia al menos una hoja, así que hay como máximo 2n nodos internos por respuesta, y copiar una respuesta cuesta O(n). El total es O(n × C(n)) = O(4^n / √n): para n = 8, se construyen directamente 1,430 cadenas en lugar de comprobar 65,536.

Algoritmo

Mantén la cadena que se está construyendo y dos contadores, opened y closed, ambos en 0.
Si la cadena tiene una longitud de 2n, guarda una copia y devuélvela.
Si opened < n, añade (, vuelve a llamar recursivamente con opened + 1 y elimínalo.
Si closed < opened, añade ), vuelve a llamar recursivamente con closed + 1 y elimínalo.
Empieza con la cadena vacía y devuelve las cadenas guardadas, que ya están ordenadas porque se prueba primero (.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Errores comunes y casos límite

Las reglas caben en dos comparaciones, así que los errores se esconden en esas comparaciones y en el orden de las dos ramas.

Permitir ) mientras closed < n en lugar de closed < opened genera cadenas como ())(, que cierran un par que nunca se abrió.
Comprobar solo que una cadena tenga tantos ( como ) acepta )(. El balance debe mantenerse en 0 o por encima en cada paso, no solo al final.
Probar ) antes que ( produce las cadenas correctas en orden inverso, y la comparación con la respuesta ordenada falla.
Guardar el búfer compartido en lugar de una copia, en un lenguaje donde las listas o los constructores de cadenas sean mutables: todas las respuestas guardadas apuntan entonces al mismo búfer, que el retroceso vuelve a vaciar.
Dimensionar una matriz de resultados fija para 2n respuestas, o para cualquier estimación pequeña: n = 8 tiene 1,430 respuestas. Aumenta el tamaño de la matriz o calcula primero el número de Catalan.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Generate Parentheses?

La solución con retroceso genera el número catalán C(n) = (2n)! / ((n+1)! n!) de cadenas, que crece como 4^n / (n^1.5 √π). Cada cadena tiene una longitud de 2n y la búsqueda nunca desperdicia una rama, por lo que el tiempo total es O(4^n / √n). El espacio adicional es O(n) para la cadena actual y la pila de llamadas, además de la salida.

¿Cuántas cadenas de paréntesis válidas hay para n pares?

Exactamente el enésimo número de Catalan: 1, 2, 5, 14, 42, 132, 429 y 1,430 para n de 1 a 8. Una forma de verlo: toda cadena bien formada es ( + A + ) + B, donde el primer ( se empareja con ese ), y A y B están bien formadas con n-1 pares entre ellas. Al sumar según el tamaño de A, se obtiene la recurrencia de Catalan.

¿Por qué cerrado < abierto garantiza una cadena válida?

Una cadena falla exactamente cuando llega un ) sin que haya antes un ( sin emparejar, es decir, cuando la cantidad de ) superaría la cantidad de (. Permitir ) solo mientras closed < opened evita que eso ocurra, y permitir ( solo mientras opened < n hace que ambas cantidades lleguen a n con una longitud de 2n. Juntas, las dos reglas describen cada prefijo de una cadena bien formada.

¿Se puede resolver Generate Parentheses sin recursión?

Sí. Mantén una pila de estados parciales, cada uno como una cadena con sus dos contadores, y amplía un estado con las mismas dos reglas. Si apilas la extensión ) antes que la extensión (, primero se desapila la de ( y la salida permanece ordenada. El trabajo es el mismo; la gestión pasa de la pila de llamadas a tu propia pila.

Python

def generateParenthesis(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

n = 3

Esperado

["((()))", "(()())", "(())()", "()(())", "()()()"]