649. Bracket Generator
A text editor must highlight every way of nesting n pairs of round brackets so that the result is balanced: each ( is closed by a later ), and no ) appears before its matching (.
Given n, return every balanced string made of exactly n opening and n closing brackets. Each string must appear exactly once, and the strings may be returned in any order. Do not build all 2^(2n) strings and filter them; extend a string only when the result can still be completed to a balanced one.
Example 1
- Input:
- n = 2
- Output:
- ["(())","()()"]
- Explanation:
Two balanced strings exist:
(())and()().
Example 2
- Input:
- n = 1
- Output:
- ["()"]
- Explanation:
A single pair can only be
().
Example 3
- Input:
- n = 3
- Output:
- ["((()))","(()())","(())()","()(())","()()()"]
- Explanation:
Five balanced strings exist for three pairs, from
((()))to()()().
Constraints
- 1 ≤
n≤ 6
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(4^n / sqrt(n))
- Space
- O(n)