Generate Parentheses

Medium#22open and close counts

You get a number n. Return every string of n "(" and n ")" that is balanced: read from the left, a ")" never comes when every "(" before it is already closed. Our example: n = 2 gives 2 strings, "(())" and "()()".

22 Generate ParenthesesWalkthrough · 1×

Example: every balanced string of 2 pairs. Watch the cut branches: at the root a ")" is ruled out because nothing is open yet, and at "((" a third "(" because both are used.

""((((()(())()()(()()s—open–close–n = 2results—
not reached yeton the way herethis step; the count lets the bracket incut off: the count rules the bracket outsaved stringfinished

Build every balanced string of 2 pairs of brackets

01/28
restart · back · play · step
Speed
1function generateParenthesis(n):
2 results = []
3 build('', 0, 0)
4 return results
5
6function build(s, open, close):
7 if len(s) == 2 * n:
8 add s to results
9 return
10 if open < n: // room for one more (
11 build(s + '(', open + 1, close)
12 if close < open: // a ( is still not closed
13 build(s + ')', open, close + 1)
state
s
–
open
–
close
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. A ")" is added only while close < open, so at every point of the string no more ")" than "(" stand before it: no string can go wrong on the way.
  2. A "(" is added only while open < n, so a string never has more than n of them; when it reaches 2n brackets, open = close = n and it is balanced.
  3. Every balanced string is reached: at each place it puts either a "(" or a ")" that the counts allow, and the run tries both. Branches the counts forbid are never entered, so nothing has to be checked at the end.

Complexity

Time O(√n × 4ⁿ): the counts let through O(4ⁿ / √n) beginnings of strings in all (they grow like the Catalan numbers), and each call builds its own string in up to 2n steps. Memory O(n²) besides the answer: the call stack is 2n deep, and each call keeps its own string of up to 2n brackets.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.