Generate Parentheses
Given an integer n, return every string of n pairs of parentheses that is well-formed (balanced), in any order. For example, with n = 2 the well-formed strings are "(())" and "()()" — but ")(" and "((" are not.
n is small (at most 8), because the number of answers grows roughly as 4^n / n^1.5 — the structure of the search matters more than micro-optimization.
Examples
- Input:
- n = 3
- Output:
- ["((()))","(()())","(())()","()(())","()()()"]
All 5 balanced arrangements of 3 pairs. 5 is the third Catalan number, the count of balanced strings.
- Input:
- n = 1
- Output:
- ["()"]
One pair has only one arrangement.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.