24 de Março
Gerar parênteses
Como usar backtracking com contadores para podar prefixos inválidos antes que eles virem trabalho desperdicado.
Backtracking Intermediario 20 min TypeScript
Dado um inteiro n, retorne todas as combinações de n pares de parenteses bem formados.
Aqui no SeniorPath, retorne as combinações na ordem natural da busca em profundidade (DFS) tentando ( antes de ) para manter a comparação deterministica.
Exemplo:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
O que perceber antes de codar
- O problema não pede qualquer string com `(` e `)`. Pede apenas as bem formadas.
- Prefixos importam. Se um prefixo já ficou inválido, nenhum sufixo salva.
- O estado necessário cabe em dois contadores e na string atual.
Erros comuns
- gerar todas as strings de tamanho `2n` e validar só no fim
- permitir mais fechamentos do que aberturas em algum prefixo
Passo 1 - Entender o que faz uma combinação ser valida
Não basta ter n aberturas e n fechamentos.
A ordem importa.
Exemplo:
"()()"e valida")(()"não e
O motivo e que, ao ler da esquerda para a direita, um fechamento nunca pode aparecer antes de existir uma abertura correspondente.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- gerar todas as strings de tamanho
2 * n - filtrar só as validas no fim
Funciona.
Mas desperdica muito trabalho com strings que já nasceram condenadas.
Passo 3 - Perguntar o que da para saber cedo
Durante a construção da string, duas regras sempre valem:
- só pode abrir se ainda faltam aberturas
- só pode fechar se já existe alguma abertura sem par
Isso significa que você pode podar muito antes de chegar no fim.
Passo 4 - Transformar a regra em backtracking
O estado necessário e pequeno:
- quantos
(já usou - quantos
)já usou - a string atual
A decisão em cada passo fica:
- tento abrir?
- tento fechar?
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function generateParenthesis(n: number): string[] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(number of valid combinations * n)
Espaço: O(n)
Solução 1 - Gerar tudo e validar depois
Boa versão inicial para enxergar onde o desperdicio entra.
function isValid(candidate: string): boolean {
let balance = 0
for (const char of candidate) {
balance += char === "(" ? 1 : -1
if (balance < 0) {
return false
}
}
return balance === 0
}
export function generateParenthesis(n: number): string[] {
const result: string[] = []
function dfs(current: string): void {
if (current.length === n * 2) {
if (isValid(current)) {
result.push(current)
}
return
}
dfs(`${current}(`)
dfs(`${current})`)
}
dfs("")
return result
}Funciona, mas gera muita coisa que nunca tinha chance de virar resposta.
Solução 2 - Backtracking com poda por contadores
Agora você evita construir prefixos inválidos.
export function generateParenthesis(n: number): string[] {
const result: string[] = []
function dfs(current: string, openUsed: number, closeUsed: number): void {
if (current.length === n * 2) {
result.push(current)
return
}
if (openUsed < n) {
dfs(`${current}(`, openUsed + 1, closeUsed)
}
if (closeUsed < openUsed) {
dfs(`${current})`, openUsed, closeUsed + 1)
}
}
dfs("", 0, 0)
return result
}O insight forte e que backtracking bom não tenta tudo. Ele tenta só o que ainda pode funcionar.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial gera todas as strings de tamanho
2ne valida depois, mas isso desperdica trabalho. A versão forte usabacktrackingcom dois contadores. Eu só abro se ainda faltam aberturas e só fecho seclose < open. Assim eu podo prefixos inválidos cedo e gero só combinações viaveis.
Isso mostra que você:
- entende a diferença entre gerar e podar
- explica a regra de validade sem vaguidao
- transforma a restrição em decisão local
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- construir resposta passo a passo
- podar prefixos inválidos cedo
- usar
backtrackingcom restrições simples - pensar em contadores e estado local
O ponto não e decorar esse problema.
O ponto e aprender a cortar busca ruim antes que ela cresca.