Generate Parentheses

Q: Qual é a complexidade de tempo de Generate Parentheses?

A solução com retrocesso gera o número de Catalan C(n) = (2n)! / ((n+1)! n!) de strings, que cresce como 4^n / (n^1.5 √π) . Cada string tem comprimento 2n e a busca nunca desperdiça um ramo, portanto o tempo total é O(4^n / √n) . O espaço extra é O(n) para a string atual e a pilha de chamadas, além da saída.

Q: Quantas strings válidas de parênteses existem para n pares?

Exatamente o n-ésimo número de Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 para n de 1 a 8. Uma maneira de ver isso: toda string bem formada é ( + A + ) + B, em que o primeiro ( corresponde àquele ) , e A e B são bem formados, com n-1 pares entre eles. Somando sobre o tamanho de A, obtemos a recorrência de Catalan.

Q: Por que closed < opened garante uma string válida?

Uma string dá errado exatamente quando um ) chega sem que haja um ( sem correspondência antes dele, o que acontece quando a contagem de ) ultrapassa a contagem de ( . Permitir ) somente enquanto closed < opened impede que isso aconteça, e permitir ( somente enquanto opened < n faz com que ambas as contagens cheguem a n no comprimento 2n . Juntas, as duas regras descrevem todo prefixo de uma string bem formada.

Q: É possível resolver Generate Parentheses sem recursão?

Sim. Mantenha uma pilha de estados parciais, cada um uma string com seus dois contadores, e estenda um estado com as mesmas duas regras. Se você empilhar a extensão ) antes da extensão ( , a extensão ( será desempilhada primeiro e a saída permanecerá ordenada. O trabalho é o mesmo; o controle passa da pilha de chamadas para a sua própria pilha.

MédioBacktracking Recursão

+10

) nunca fica à frente do número de (, e as duas contagens são iguais no final. Portanto, (())() é bem formada, enquanto ())( não é: seu terceiro caractere fecha um par que nunca foi aberto.

Você recebe um inteiro n. Retorne todas as cadeias bem formadas compostas por n parênteses de abertura e n parênteses de fechamento, em ordem lexicográfica, na qual ( vem antes de ).

Função

generateParenthesis(n: integer) → string-array

ninteger: o número de pares de parênteses
Retornastring-array: toda sequência bem formada de n pares, em ordem lexicográfica

Restrições

1 ≤ n ≤ 8
Para n = 8, a resposta contém 1.430 strings.

Exemplos

Entrada: n = 3
Saída: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explicação: Três pares podem ser organizados de cinco maneiras bem formadas. ((())) abre os três antes de fechar qualquer um e, como ( vem primeiro na ordenação, aparece no início da lista; ()()() fecha cada par imediatamente e aparece no final.

Entrada: n = 1
Saída: ["()"]
Explicação: Um par tem um único arranjo bem formado. A única outra sequência com um ( e um ) é )(, que se fecha antes que algo esteja aberto.

+10 testes ocultos ao enviar

Para ir além

Você consegue contar as strings bem formadas para n pares sem gerá-las?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Apenas uma pequena parcela das strings de comprimento 2n é bem formada: 5 das 64 strings para n = 3 e 1.430 das 65.536 para n = 8. A ideia para resolver isso é construir a string da esquerda para a direita e adicionar somente caracteres que a mantenham válida, para que a busca nunca entre em um ramo que não possa ser concluído. Dois contadores determinam o que é permitido: quantos ( você colocou e quantos ). Tentar ( antes de ) em cada etapa faz com que as strings já saiam ordenadas.

Construa cada string e, em seguida, verifique-a

Intuição

A maneira direta é preencher as 2n posições de todas as formas possíveis e manter as strings bem formadas. Cada posição contém ( ou ), então há 2^(2n) = 4^n strings. Uma função recursiva coloca ( na próxima posição, faz a chamada recursiva, depois coloca ) nessa posição e faz outra chamada recursiva, e cada string concluída passa por uma verificação.

A verificação percorre a string mantendo um saldo: mais 1 para (, menos 1 para ). A string está bem formada quando o saldo nunca fica abaixo de 0 e termina em 0. Ficar abaixo de 0 significa que há um ) sem nada aberto para fechar, como no terceiro caractere de ())(.

Tentar ( antes de ) em cada posição lista as strings em ordem lexicográfica, porque ( vem antes de ) na ordenação. Portanto, as strings mantidas já estão ordenadas.

O custo é de 4^n strings, cada uma verificada em O(n). Para n = 8, são 65.536 strings para 1.430 respostas, então cerca de 98% do trabalho é descartado. O processo termina aqui porque n é no máximo 8, mas o número de strings quadruplica a cada par adicional, e o algoritmo continua construindo strings que começam com ), embora o primeiro caractere já seja suficiente para descartá-las.

Algoritmo

Mantenha um buffer de 2n caracteres e uma lista para as respostas.
Escreva fill(pos). Se pos for igual a 2n, verifique o buffer e salve-o se estiver bem formado.
Caso contrário, coloque ( em pos e chame fill(pos + 1); em seguida, coloque ) nessa posição e chame a função novamente.
Para verificar uma string, some 1 para cada ( e subtraia 1 para cada ). Rejeite-a assim que o saldo ficar abaixo de 0 ou se não terminar em 0.
Chame fill(0) e retorne as strings salvas, já 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

Recuar nas contagens de abertura e fechamento

Intuição

Mova a verificação para a construção. Um prefixo ainda pode se tornar uma string bem formada exatamente quando duas regras são satisfeitas: ele usa no máximo n parênteses de abertura e nunca tem mais ) do que (. Portanto, a cada passo, você pode adicionar ( enquanto opened < n e ) enquanto closed < opened. Quando a string chega ao comprimento 2n, ambas as contagens são n e a string está bem formada, sem mais nada para verificar.

Aqui está a árvore completa para n = 2. A partir da string vazia, apenas ( é permitido, pois ainda não há nada aberto. A partir de (, ambos são permitidos. No ramo ((, opened já é 2, então apenas ) cabe, duas vezes, formando (()). No ramo (), nada está aberto, então apenas ( cabe, depois ), formando ()(). Cada ramo termina em uma resposta: a busca nunca constrói uma string que precise descartar.

Nenhuma resposta é perdida. Todo prefixo de uma string bem formada obedece às duas regras, então a busca nunca recusa o próximo caractere de que essa string precisa, e cada string é produzida uma única vez, pois seus caracteres descrevem um único caminho pela árvore. A ordem funciona como na primeira abordagem: duas strings diferem primeiro no ponto em que seus caminhos se dividem, e o ramo ( nesse ponto é explorado primeiro.

Toda folha é uma resposta, e o número de respostas para n pares é o número de Catalan C(n), que cresce como 4^n / (n^1.5 √π). Cada nó interno está no caminho para pelo menos uma folha, então há no máximo 2n nós internos por resposta, e copiar uma resposta custa O(n). O total é O(n × C(n)) = O(4^n / √n): para n = 8, são construídas diretamente 1.430 strings, em vez de verificar 65.536.

Algoritmo

Mantenha a string que está sendo construída e dois contadores, opened e closed, ambos iguais a 0.
Se a string tiver comprimento 2n, salve uma cópia dela e retorne.
Se opened < n, adicione (, faça a recursão com opened + 1 e remova-o.
Se closed < opened, adicione ), faça a recursão com closed + 1 e remova-o.
Comece com a string vazia e retorne as strings salvas, já ordenadas porque ( é testado primeiro.

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

Armadilhas e casos extremos

As regras cabem em duas comparações, então os bugs ficam escondidos nessas comparações e na ordem dos dois ramos.

Permitir ) quando closed < n, em vez de closed < opened, gera strings como ())(, que fecham um par que nunca foi aberto.
Verificar apenas se uma string contém a mesma quantidade de ( e ) aceita )(. O saldo precisa permanecer em 0 ou acima em cada etapa, não apenas no final.
Tentar ) antes de ( produz as strings corretas na ordem inversa, e a comparação com a resposta ordenada falha.
Salvar o buffer compartilhado em vez de uma cópia, em uma linguagem na qual listas ou construtores de strings sejam mutáveis: então, cada resposta salva aponta para o mesmo buffer, que o retrocesso esvazia novamente.
Dimensionar um array fixo de resultados para 2n respostas, ou usar qualquer estimativa pequena: n = 8 tem 1,430 respostas. Aumente o array ou calcule primeiro o número de Catalan.

Perguntas frequentes4

Qual é a complexidade de tempo de Generate Parentheses?

A solução com retrocesso gera o número de Catalan C(n) = (2n)! / ((n+1)! n!) de strings, que cresce como 4^n / (n^1.5 √π). Cada string tem comprimento 2n e a busca nunca desperdiça um ramo, portanto o tempo total é O(4^n / √n). O espaço extra é O(n) para a string atual e a pilha de chamadas, além da saída.

Quantas strings válidas de parênteses existem para n pares?

Exatamente o n-ésimo número de Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 para n de 1 a 8. Uma maneira de ver isso: toda string bem formada é ( + A + ) + B, em que o primeiro ( corresponde àquele ), e A e B são bem formados, com n-1 pares entre eles. Somando sobre o tamanho de A, obtemos a recorrência de Catalan.

Por que closed < opened garante uma string válida?

Uma string dá errado exatamente quando um ) chega sem que haja um ( sem correspondência antes dele, o que acontece quando a contagem de ) ultrapassa a contagem de (. Permitir ) somente enquanto closed < opened impede que isso aconteça, e permitir ( somente enquanto opened < n faz com que ambas as contagens cheguem a n no comprimento 2n. Juntas, as duas regras descrevem todo prefixo de uma string bem formada.

É possível resolver Generate Parentheses sem recursão?

Sim. Mantenha uma pilha de estados parciais, cada um uma string com seus dois contadores, e estenda um estado com as mesmas duas regras. Se você empilhar a extensão ) antes da extensão (, a extensão ( será desempilhada primeiro e a saída permanecerá ordenada. O trabalho é o mesmo; o controle passa da pilha de chamadas para a sua própria pilha.

Python

def generateParenthesis(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

n = 3

Esperado

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