Generate Parentheses
Medium · Backtracking · String · Dynamic Programming · Backtracking
Problem
Given n, return every string of n opening brackets ( and n closing brackets ) that is balanced: reading from the left, each ) closes an earlier ( that is still open, and nothing is left open at the end. Return the strings in any order.
Having as many ( as ) is not enough. "())(()" has three of each, but its third character closes a bracket that was never opened. In a balanced string, no prefix ever has more ) than (.
Examples
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Five arrangements of three pairs are balanced. Each starts with an opening bracket and ends with a closing one.
Input: n = 1 Output: ["()"]
One pair can be written only one way: in )( the closing bracket comes before anything is open.
Constraints
- 1 <= n <= 8
Approaches
- Generate every bracket string, keep the balanced ones — time O(n · 4^n), space O(n · C(n))
Related problems
Start free on Cariara · Coding problems · System design studio
