Generate Parentheses

Q: Quelle est la complexité temporelle de Generate Parentheses ?

Le retour arrière génère C(n) = (2n)! / ((n+1)! n!) chaînes, le nombre de Catalan, qui croît comme 4^n / (n^1.5 √π) . Chacune nécessite O(n) pour être construite et copiée, donc la complexité temporelle est O(4^n / √n) . L’espace supplémentaire est de O(n) pour la chaîne actuelle et la pile d’appels, sans compter la sortie.

Q: Combien existe-t-il de chaînes de parenthèses valides pour n paires ?

Les nombres de Catalan d’indice n : 1, 2, 5, 14, 42, 132, 429 et 1 430 pour n de 1 à 8. Toute chaîne bien formée se décompose en ( A ) B, où ce ) correspond à la première ( et où A et B ont en commun n - 1 paires. La somme selon la taille de A donne la récurrence de Catalan.

Q: Peut-on résoudre Generate Parentheses sans récursion ?

Oui. Gardez une pile d’états partiels, chacun étant une chaîne contenant ses deux compteurs, et prolongez chaque état selon les mêmes deux règles. Empilez l’extension ) avant celle ( , afin que celle avec ( soit dépilée en premier et que la sortie reste triée.

MoyenRetour sur trace Récursivité

+10

Une chaîne de parenthèses est bien formée lorsque, en la lisant de gauche à droite, le nombre de ) ne dépasse jamais celui de (, et que les deux nombres sont égaux à la fin. Ainsi, (())() est bien formée, tandis que ())( ne l’est pas : son troisième caractère ferme une paire qui n’a jamais été ouverte.

Étant donné un entier n, renvoie toutes les chaînes bien formées composées de n parenthèses ouvrantes et de n parenthèses fermantes, triées dans l’ordre lexicographique, où ( précède ).

Fonction

generateParenthesis(n: integer) → string-array

ninteger: le nombre de paires de parenthèses
Renvoiestring-array: chaque chaîne bien formée de n paires, dans l’ordre lexicographique

Contraintes

1 ≤ n ≤ 8
Pour n = 8, la réponse contient 1 430 chaînes.

Exemples

Entrée: n = 3
Sortie: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explication: Trois paires donnent cinq chaînes bien formées. ((())) ouvre les trois d’abord, donc cette chaîne est en premier dans l’ordre de tri ; ()()() ferme chaque paire immédiatement et vient en dernier.

Entrée: n = 1
Sortie: ["()"]
Explication: Une paire contient une chaîne bien formée. Le seul autre arrangement, )(, se ferme avant que quoi que ce soit ne soit ouvert.

Pour aller plus loin

Peux-tu compter les chaînes bien formées pour n paires sans les générer ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Peu de chaînes de longueur 2n sont bien formées : 1 430 sur 65 536 pour n = 8. Construis chaque chaîne de gauche à droite et n’ajoute un caractère que si le préfixe peut encore être complété. Deux compteurs permettent de le déterminer, et essayer ( avant ) trie les chaînes obtenues.

Construisez chaque chaîne, puis vérifiez-la

Intuition

Remplis les 2n positions avec tous les mélanges de ( et ), soit 4^n chaînes, puis conserve celles qui sont bien formées. Pour vérifier une chaîne, parcours-la en maintenant un bilan : ajoute 1 pour (, soustrais 1 pour ). Elle est bien formée si le bilan ne passe jamais sous 0 et se termine à 0. Placer ( avant ) à chaque position énumère les chaînes dans l’ordre trié.

La vérification de chaque chaîne coûte O(n). Pour n = 8, cela représente 65,536 chaînes pour 1,430 réponses ; environ 98 % du travail est donc inutile, et le nombre de chaînes quadruple à chaque paire supplémentaire.

Algorithme

Conservez un tampon de 2n caractères et une liste pour les réponses.
fill(pos) : si pos est égal à 2n, enregistrez le tampon s’il est bien formé.
Sinon, placez ( à la position pos et appelez fill(pos + 1), puis placez ) à cette position et appelez à nouveau cette fonction.
Pour vérifier, ajoutez 1 pour chaque ( et soustrayez 1 pour chaque ). Rejetez la chaîne si le solde devient inférieur à 0 ou ne se termine pas à 0.
Appelez fill(0) et renvoyez les chaînes enregistrées.

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

Revenir en arrière sur les nombres d’ouvertures et de fermetures

Intuition

Déplace la vérification dans la construction. Un préfixe peut devenir une chaîne bien formée exactement lorsqu’il utilise au plus n ( et qu’il n’a jamais plus de ) que de (. Ainsi, ( est autorisée tant que opened < n, et ) tant que closed < opened. À la longueur 2n, les deux compteurs valent n, et la chaîne est bien formée : il ne reste rien à vérifier.

Aucune réponse n’est omise, car chaque préfixe d’une chaîne bien formée respecte les deux règles. Aucune branche n’est inutile : pour n = 2, la branche (( ne peut se refermer que deux fois, donnant (()), et la branche () ne peut qu’ouvrir puis fermer, donnant ()(). Chaque chaîne correspond à un chemin dans l’arbre, elle apparaît donc une seule fois, et la branche ( est explorée en premier, ce qui trie la sortie.

Chaque feuille est une réponse, le travail est donc proportionnel à la sortie : O(4^n / √n).

Algorithme

Conservez la chaîne en cours de construction et deux compteurs, opened et closed, tous deux à 0.
Si la chaîne a une longueur de 2n, enregistrez-en une copie et retournez.
Si opened < n, ajoutez (, appelez récursivement avec opened + 1, puis retirez-le.
Si closed < opened, ajoutez ), appelez récursivement avec closed + 1, puis retirez-le.
Commencez avec la chaîne vide et renvoyez les chaînes enregistrées.

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

Pièges et cas limites

Autoriser ) lorsque closed < n au lieu de closed < opened. Cela construit ())(, qui ferme une paire qui n’a jamais été ouverte.
Vérifier uniquement que les nombres correspondent à la fin. Cela accepte )( ; l’équilibre doit rester supérieur ou égal à 0 à chaque étape.
Essayer ) avant (. Les bonnes chaînes sont alors générées dans l’ordre inverse.
Enregistrer le tampon partagé au lieu d’une copie, lorsque les listes ou les constructeurs de chaînes sont modifiables. Chaque réponse enregistrée affiche alors le même tampon, que le retour arrière vide à nouveau.
Dimensionner un tableau de résultats fixe à partir d’une estimation trop basse. n = 8 donne 1 430 réponses.

Questions fréquentes3

Quelle est la complexité temporelle de Generate Parentheses ?

Le retour arrière génère C(n) = (2n)! / ((n+1)! n!) chaînes, le nombre de Catalan, qui croît comme 4^n / (n^1.5 √π). Chacune nécessite O(n) pour être construite et copiée, donc la complexité temporelle est O(4^n / √n). L’espace supplémentaire est de O(n) pour la chaîne actuelle et la pile d’appels, sans compter la sortie.

Combien existe-t-il de chaînes de parenthèses valides pour n paires ?

Les nombres de Catalan d’indice n : 1, 2, 5, 14, 42, 132, 429 et 1 430 pour n de 1 à 8. Toute chaîne bien formée se décompose en ( A ) B, où ce ) correspond à la première ( et où A et B ont en commun n - 1 paires. La somme selon la taille de A donne la récurrence de Catalan.

Peut-on résoudre Generate Parentheses sans récursion ?

Oui. Gardez une pile d’états partiels, chacun étant une chaîne contenant ses deux compteurs, et prolongez chaque état selon les mêmes deux règles. Empilez l’extension ) avant celle (, afin que celle avec ( soit dépilée en premier et que la sortie reste triée.

def generateParenthesis(n):
    # Écrivez le code ici

Test #1

Test #2

Argument

n = 3

Résultat attendu

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