Generate Parentheses

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

La solution par retour sur trace produit le nombre de Catalan C(n) = (2n)! / ((n+1)! n!) de chaînes, qui croît comme 4^n / (n^1.5 √π) . Chaque chaîne a une longueur de 2n et la recherche ne gaspille jamais de branche ; le temps total est donc O(4^n / √n) . L’espace supplémentaire est de O(n) pour la chaîne en cours et la pile d’appels, en plus de la sortie.

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

Exactement le nᵉ nombre de Catalan : 1, 2, 5, 14, 42, 132, 429 et 1 430 pour n de 1 à 8. Une façon de le voir : toute chaîne bien formée est ( + A + ) + B, où le premier ( est apparié à ce ) , et A et B sont bien formés avec n-1 paires au total. En faisant la somme sur la taille de A, on obtient la récurrence de Catalan.

Q: Pourquoi closed < opened garantit-il une chaîne valide ?

Une chaîne est incorrecte exactement lorsqu’un ) arrive sans ( non apparié avant lui, c’est-à-dire lorsque le nombre de ) dépasserait le nombre de ( . N’autoriser ) que lorsque closed < opened empêche que cela se produise, et n’autoriser ( que lorsque opened < n fait atteindre n aux deux nombres à la longueur 2n . Ensemble, ces deux règles décrivent chaque préfixe d’une chaîne bien formée.

Q: Peut-on résoudre le problème « Generate Parentheses » sans récursion ?

Oui. Gardez une pile d’états partiels, chacun étant une chaîne avec ses deux compteurs, et prolongez un état en appliquant les mêmes deux règles. Si vous empilez l’extension ) avant l’extension ( , celle avec ( est dépilée en premier et la sortie reste triée. Le travail est le même ; la gestion des états passe de la pile d’appels à votre propre pile.

MoyenRetour sur trace Récursivité

+10

Une chaîne de parenthèses est bien formée lorsque, lue 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, contrairement à ())( : son troisième caractère ferme une paire qui n’a jamais été ouverte.

On vous donne un entier n. Renvoyez 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: toute chaîne bien formée de n paires, dans l’ordre lexicographique

Contraintes

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

Exemples

Entrée: n = 3
Sortie: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explication: Trois paires peuvent être disposées de cinq façons bien formées. ((())) ouvre les trois avant d’en fermer une, et puisque ( se trie en premier, cette forme ouvre la liste ; ()()() ferme chaque paire aussitôt et arrive en dernier.

Entrée: n = 1
Sortie: ["()"]
Explication: Une paire possède une seule disposition bien formée. La seule autre chaîne composée d’une ( et d’une ) est )(, qui se ferme avant que quoi que ce soit ne soit ouvert.

+10 tests cachés à la soumission

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

Seule une petite partie des chaînes de longueur 2n sont bien formées : 5 des 64 chaînes pour n = 3, et 1 430 des 65 536 pour n = 8. L’idée qui résout le problème consiste à construire la chaîne de gauche à droite et à n’ajouter qu’un caractère qui la maintient valide, afin que la recherche ne s’engage jamais dans une branche qui ne peut pas aboutir. Deux compteurs déterminent ce qui est autorisé : le nombre de ( que tu as placées et le nombre de ). Essayer ( avant ) à chaque étape fait que les chaînes sont déjà triées à la sortie.

Construis chaque chaîne, puis vérifie-la

Intuition

La méthode directe consiste à remplir les 2n positions de toutes les façons possibles et à conserver les chaînes bien formées. Chaque position contient ( ou ), il y a donc 2^(2n) = 4^n chaînes. Une fonction récursive place ( à la position suivante, s’appelle à nouveau, puis y place ) et s’appelle à nouveau, et chaque chaîne terminée est vérifiée.

La vérification parcourt la chaîne en maintenant un solde : plus 1 pour (, moins 1 pour ). La chaîne est bien formée lorsque le solde ne devient jamais inférieur à 0 et se termine à 0. Un solde inférieur à 0 correspond à un ) qui n’a aucune parenthèse ouvrante à fermer, comme au troisième caractère de ())(.

Essayer ( avant ) à chaque position énumère les chaînes dans l’ordre lexicographique, car ( précède ) dans l’ordre de tri. Les chaînes conservées sont donc déjà triées.

Le coût est de 4^n chaînes, chacune vérifiée en O(n). Pour n = 8, cela représente 65 536 chaînes pour 1 430 réponses, donc environ 98 % du travail est inutile. La méthode fonctionne ici parce que n est au plus égal à 8, mais le nombre de chaînes est multiplié par quatre à chaque paire supplémentaire, et elle continue à construire des chaînes commençant par ) alors que le premier caractère suffit déjà à les éliminer.

Algorithme

Gardez un tampon de 2n caractères et une liste pour les réponses.
Écrivez fill(pos). Si pos est égal à 2n, vérifiez le tampon et enregistrez-le s’il est bien formé.
Sinon, placez ( à pos et appelez fill(pos + 1), puis placez ) à cet endroit et appelez à nouveau la fonction.
Pour vérifier une chaîne, ajoutez 1 pour chaque ( et soustrayez 1 pour chaque ). Rejetez-la dès que le solde devient inférieur à 0, ou s’il ne se termine pas à 0.
Appelez fill(0) et renvoyez les chaînes enregistrées, déjà trié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 le contrôle à l’intérieur de la construction. Un préfixe peut encore être complété en une chaîne bien formée exactement lorsque deux règles sont respectées : il utilise au plus n parenthèses ouvrantes, et il ne contient jamais plus de ) que de (. Ainsi, à chaque étape, tu peux ajouter ( tant que opened < n, et ) tant que closed < opened. Lorsque la chaîne atteint la longueur 2n, les deux nombres sont égaux à n et la chaîne est bien formée, sans qu’il reste quoi que ce soit à vérifier.

Voici l’arbre complet pour n = 2. À partir de la chaîne vide, seul ( est autorisé, puisque rien n’est encore ouvert. À partir de (, les deux caractères sont autorisés. Dans la branche ((, opened vaut déjà 2, donc seul ) convient, deux fois, ce qui donne (()). Dans la branche (), rien n’est ouvert, donc seul ( convient, puis ), ce qui donne ()(). Chaque branche aboutit à une réponse : la recherche ne construit jamais de chaîne qu’elle doit ensuite éliminer.

Aucune réponse n’est oubliée. Chaque préfixe d’une chaîne bien formée respecte les deux règles, donc la recherche ne refuse jamais le caractère dont cette chaîne a besoin à l’étape suivante, et chaque chaîne est produite une seule fois, puisque ses caractères dessinent un chemin unique dans l’arbre. L’ordre est le même que dans la première approche : deux chaînes diffèrent d’abord à l’endroit où leurs chemins se séparent, et la branche ( y est explorée en premier.

Chaque feuille est une réponse, et le nombre de réponses pour n paires est le nombre de Catalan C(n), qui croît comme 4^n / (n^1.5 √π). Chaque nœud interne se trouve sur le chemin menant à au moins une feuille, donc il y a au plus 2n nœuds internes par réponse, et copier une réponse coûte O(n). Le coût total est O(n × C(n)) = O(4^n / √n) : pour n = 8, 1 430 chaînes construites directement au lieu de 65 536 chaînes vérifiées.

Algorithme

Conserve la chaîne en cours de construction et deux compteurs, opened et closed, tous deux initialisés à 0.
Si la chaîne a une longueur de 2n, enregistre-en une copie et retourne.
Si opened < n, ajoute (, rappelle la fonction avec opened + 1, puis supprime-le.
Si closed < opened, ajoute ), rappelle la fonction avec closed + 1, puis supprime-le.
Commence avec la chaîne vide et retourne les chaînes enregistrées, déjà triées puisque ( est essayé en premier.

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

Les règles tiennent en deux comparaisons, donc les bugs se cachent dans ces comparaisons et dans l’ordre des deux branches.

Autoriser ) lorsque closed < n au lieu de closed < opened construit des chaînes telles que ())(, qui ferment une paire qui n’a jamais été ouverte.
Vérifier uniquement qu’une chaîne contient autant de ( que de ) accepte )(. L’équilibre doit rester supérieur ou égal à 0 à chaque étape, pas seulement à la fin.
Essayer ) avant ( produit les bonnes chaînes dans l’ordre inverse, et la comparaison avec la réponse triée échoue.
Enregistrer le tampon partagé au lieu d’une copie, dans un langage où les listes ou les constructeurs de chaînes sont modifiables : chaque réponse enregistrée pointe alors vers le même tampon, que le retour arrière vide à nouveau.
Prévoir un tableau de résultats fixe de taille 2n, ou toute autre petite estimation : n = 8 donne 1,430 réponses. Agrandissez le tableau ou calculez d’abord le nombre de Catalan.

Questions fréquentes4

Quelle est la complexité temporelle de Generate Parentheses ?

La solution par retour sur trace produit le nombre de Catalan C(n) = (2n)! / ((n+1)! n!) de chaînes, qui croît comme 4^n / (n^1.5 √π). Chaque chaîne a une longueur de 2n et la recherche ne gaspille jamais de branche ; le temps total est donc O(4^n / √n). L’espace supplémentaire est de O(n) pour la chaîne en cours et la pile d’appels, en plus de la sortie.

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

Exactement le nᵉ nombre de Catalan : 1, 2, 5, 14, 42, 132, 429 et 1 430 pour n de 1 à 8. Une façon de le voir : toute chaîne bien formée est ( + A + ) + B, où le premier ( est apparié à ce ), et A et B sont bien formés avec n-1 paires au total. En faisant la somme sur la taille de A, on obtient la récurrence de Catalan.

Pourquoi closed < opened garantit-il une chaîne valide ?

Une chaîne est incorrecte exactement lorsqu’un ) arrive sans ( non apparié avant lui, c’est-à-dire lorsque le nombre de ) dépasserait le nombre de (. N’autoriser ) que lorsque closed < opened empêche que cela se produise, et n’autoriser ( que lorsque opened < n fait atteindre n aux deux nombres à la longueur 2n. Ensemble, ces deux règles décrivent chaque préfixe d’une chaîne bien formée.

Peut-on résoudre le problème « Generate Parentheses » sans récursion ?

Oui. Gardez une pile d’états partiels, chacun étant une chaîne avec ses deux compteurs, et prolongez un état en appliquant les mêmes deux règles. Si vous empilez l’extension ) avant l’extension (, celle avec ( est dépilée en premier et la sortie reste triée. Le travail est le même ; la gestion des états passe de la pile d’appels à votre propre pile.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

n = 3

Attendu

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