Generate Parentheses

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

La búsqueda con retroceso genera C(n) = (2n)! / ((n+1)! n!) cadenas, el número de Catalan, que crece como 4^n / (n^1.5 √π) . Cada una requiere O(n) para construirse y copiarse, así que el tiempo 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?

El n.º de Catalan: 1, 2, 5, 14, 42, 132, 429 y 1,430 para n de 1 a 8. Toda cadena bien formada se divide en ( A ) B, donde ese ) coincide con el primer ( y A y B comparten n - 1 pares. Al sumar según el tamaño de A, se obtiene la recurrencia de Catalan.

Q: ¿Se puede resolver Generar paréntesis sin recursión?

Sí. Mantén una pila de estados parciales, cada uno como una cadena con sus dos contadores, y amplía cada estado con las mismas dos reglas. Inserta primero la extensión ) y luego la extensión ( , para que la extensión ( se extraiga primero y la salida siga ordenada.

MedioBacktracking Recursión

+10

Una cadena de paréntesis está bien formada cuando, al leerla de izquierda a derecha, la cantidad de ) nunca supera la cantidad de (, y ambas cantidades son iguales al final. Por lo tanto, (())() está bien formada, mientras que ())( no lo está: su tercer carácter cierra un par que nunca se abrió.

Dado un entero n, devuelve todas las cadenas bien formadas con 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 forman cinco cadenas bien formadas. ((())) abre los tres pares primero, así que se ordena primero; ()()() cierra cada par de inmediato y queda al final.

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

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

Pocas cadenas de longitud 2n están bien formadas: 1.430 de 65.536 para n = 8. Construye cada cadena de izquierda a derecha y añade un carácter solo cuando el prefijo aún pueda completarse. Dos contadores lo determinan, y probar ( antes que ) hace que las cadenas salgan ordenadas.

Construye cada cadena y después compruébala

Intuición

Rellena las 2n posiciones con todas las combinaciones de ( y ), 4^n cadenas, y conserva las que estén bien formadas. Para comprobar una cadena, recórrela llevando un balance: suma 1 por cada ( y resta 1 por cada ). Está bien formada cuando el balance nunca baja de 0 y termina en 0. Colocar ( antes de ) en cada posición enumera las cadenas en orden ordenado.

Comprobar cada cadena cuesta O(n). Para n = 8, son 65,536 cadenas para 1,430 respuestas, así que se descarta alrededor del 98% del trabajo, y la cantidad se cuadruplica con cada par adicional.

Algoritmo

Mantén un búfer de 2n caracteres y una lista para las respuestas.
fill(pos): si pos es igual a 2n, guarda el búfer cuando esté bien formado.
De lo contrario, coloca ( en pos y llama a fill(pos + 1); después coloca ) allí y vuelve a llamarla.
Para comprobarlo, suma 1 por cada ( y resta 1 por cada ). Rechaza la secuencia cuando el balance sea menor que 0 o no termine en 0.
Llama a fill(0) y devuelve las cadenas guardadas.

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

Retroceder en los recuentos de apertura y cierre

Intuición

Mueve la comprobación al proceso de construcción. Un prefijo puede crecer hasta convertirse en una cadena bien formada exactamente cuando usa como máximo n caracteres ( y nunca tiene más ) que (. Así que se permite ( mientras opened < n, y ) mientras closed < opened. Con una longitud de 2n, ambos recuentos son n, y la cadena está bien formada sin que quede nada por comprobar.

No se omite ninguna respuesta, porque todos los prefijos de una cadena bien formada cumplen ambas reglas. No se desperdicia ninguna rama: para n = 2, la rama (( solo puede cerrarse dos veces, lo que da (()), y la rama () solo puede abrirse y cerrarse, lo que da ()(). Cada cadena corresponde a un único recorrido del árbol, así que aparece una sola vez, y la rama ( se explora primero, por lo que la salida queda ordenada.

Hojas son respuestas, así que el trabajo es proporcional a la salida: O(4^n / √n).

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.

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

Permitir ) mientras closed < n en lugar de closed < opened. Eso construye ())(, que cierra un par que nunca se abrió.
Comprobar únicamente que las cantidades coincidan al final. Eso acepta )(; el balance debe mantenerse en 0 o por encima en cada paso.
Probar ) antes que (. Las cadenas correctas salen en orden inverso.
Guardar el búfer compartido en lugar de una copia, cuando las listas o los constructores de cadenas son mutables. Todas las respuestas guardadas muestran entonces el mismo búfer, que el retroceso vuelve a vaciar.
Dimensionar una matriz de resultados de tamaño fijo basándose en una estimación pequeña. n = 8 tiene 1,430 respuestas.

Preguntas frecuentes3

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

La búsqueda con retroceso genera C(n) = (2n)! / ((n+1)! n!) cadenas, el número de Catalan, que crece como 4^n / (n^1.5 √π). Cada una requiere O(n) para construirse y copiarse, así que el tiempo 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?

El n.º de Catalan: 1, 2, 5, 14, 42, 132, 429 y 1,430 para n de 1 a 8. Toda cadena bien formada se divide en ( A ) B, donde ese ) coincide con el primer ( y A y B comparten n - 1 pares. Al sumar según el tamaño de A, se obtiene la recurrencia de Catalan.

¿Se puede resolver Generar paréntesis sin recursión?

Sí. Mantén una pila de estados parciales, cada uno como una cadena con sus dos contadores, y amplía cada estado con las mismas dos reglas. Inserta primero la extensión ) y luego la extensión (, para que la extensión ( se extraiga primero y la salida siga ordenada.

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

Prueba #1

Prueba #2

Argumento

n = 3

Salida Esperada

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