DSA Tracker

Visualize

Generate Parentheses

Add '(' whenever possible, ')' only when it stays valid

time O(4^n / sqrt(n))space O(n) recursion depth

Instead of generating every possible string of length 2n and filtering out the invalid ones, build only valid strings from the start: track how many '(' and ')' have been placed, allow a '(' whenever fewer than n have been used, and allow a ')' only when fewer close-brackets than open-brackets have been placed so far (otherwise it would go negative-balance, i.e. invalid). Every complete path this reaches is automatically well-formed.

Details

Animated on: n = 3 — generate all combinations of 3 well-formed pairs of parentheses.

Problem:Generate ParenthesesMedium

Add '(' whenever possible, ')' only when it stays valid

step 1 / 28

n=3: build every valid combination of 3 pairs by backtracking. A '(' can be added anytime we haven't used all 3 yet; a ')' can only be added if it wouldn't outnumber the '(' placed so far (else the string becomes invalid).

Pseudocode
1FUNCTION backtrack(path, open, close):
2  IF open equals n and close equals n:
3    add path to results; RETURN
4  IF open < n:
5    backtrack(path + '(', open+1, close)   (add an open bracket)
6  IF close < open:
7    backtrack(path + ')', open, close+1)   (add a close bracket only while it stays valid)

← / → step · space play · Home restart

Every step in words

Show all 28 steps
  1. n=3: build every valid combination of 3 pairs by backtracking. A '(' can be added anytime we haven't used all 3 yet; a ')' can only be added if it wouldn't outnumber the '(' placed so far (else the string becomes invalid).
  2. Add '(' -> "(" (open=1, close=0).
  3. Add '(' -> "((" (open=2, close=0).
  4. Add '(' -> "(((" (open=3, close=0).
  5. Add ')' -> "((()" (open=3, close=1) — valid since close < open so far.
  6. Add ')' -> "((())" (open=3, close=2) — valid since close < open so far.
  7. Add ')' -> "((()))" (open=3, close=3) — valid since close < open so far.
  8. Complete: "((()))" is valid (3 of each, never unbalanced). Combination #1.
  9. Add ')' -> "(()" (open=2, close=1) — valid since close < open so far.
  10. Add '(' -> "(()(" (open=3, close=1).
  11. Add ')' -> "(()()" (open=3, close=2) — valid since close < open so far.
  12. Add ')' -> "(()())" (open=3, close=3) — valid since close < open so far.
  13. Complete: "(()())" is valid (3 of each, never unbalanced). Combination #2.
  14. Add ')' -> "(())" (open=2, close=2) — valid since close < open so far.
  15. Add '(' -> "(())(" (open=3, close=2).
  16. Add ')' -> "(())()" (open=3, close=3) — valid since close < open so far.
  17. Complete: "(())()" is valid (3 of each, never unbalanced). Combination #3.
  18. Add ')' -> "()" (open=1, close=1) — valid since close < open so far.
  19. Add '(' -> "()(" (open=2, close=1).
  20. Add '(' -> "()((" (open=3, close=1).
  21. Add ')' -> "()(()" (open=3, close=2) — valid since close < open so far.
  22. Add ')' -> "()(())" (open=3, close=3) — valid since close < open so far.
  23. Complete: "()(())" is valid (3 of each, never unbalanced). Combination #4.
  24. Add ')' -> "()()" (open=2, close=2) — valid since close < open so far.
  25. Add '(' -> "()()(" (open=3, close=2).
  26. Add ')' -> "()()()" (open=3, close=3) — valid since close < open so far.
  27. Complete: "()()()" is valid (3 of each, never unbalanced). Combination #5.
  28. All 5 valid combinations for n=3: ((())), (()()), (())(), ()(()), ()()().

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Generate Parentheses in the editorAll Backtracking problemsBack to roadmap