Generate Parentheses
The key idea
Build the string one character at a time. You may add
( only while the count of opens is below n, and you may add ) only while the count of closes is still below the count of opens. Those two rules keep every prefix valid, so you never waste time on a string that can fail.Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
A string of parentheses is well-formed when every ( has a matching ) that comes after it, and the pairs are properly nested. Return the answers in any order, but each combination must use exactly n opening and n closing parentheses.
Constraints
1 <= n <= 8
Examples
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1
Output: ["()"]
Complexity
Time: O(4^n / sqrt(n)) Space: O(4^n / sqrt(n))
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM
- PermutationsMEDIUM