Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Generate Parentheses

LeetCode #22Medium
Add '(' or ')' with validity pruning

Given an integer n, return all distinct strings of n pairs of parentheses that are well-formed (every opening parenthesis is properly matched and closed).

Asked atAmazonGoogleMetaUber
step 1 / 36
add '(' or ')' with validity pruning
((()))
((())
((()
(((
(()())
(()()
(()(
(())()
(())(
(()))
(())
(()
((
()(())
()(()
()((
()()()
()()(
()())
()()
()(
())
()
(
)
ε
valid strings
(none yet)
Backtracking · open/close counters with pruning
▸
1gen(s, opens, closes):
2    if s.length == 2n: record s; return    // complete
3    // choose ( while opens < n
4    if opens < n:
5        gen(s + "(", opens + 1, closes)
6    // choose ) while closes < opens, else prune
7    if closes < opens:
8        gen(s + ")", opens, closes + 1)
9    return                                 // un-choose by returning
10// answer = all recorded strings
state
  • n3
  • goal5 valid strings

line 1Generate all well-formed strings of 3 pairs of parentheses. We build them one character at a time. At each node we may add "(" while we still have opens left, or ")" while there are unmatched opens to close. The tree below is the whole space of these choices.