DSA problem
Generate Parentheses
Given an integer n, generate all combinations of well-formed parentheses of length 2 * n. A combination is well-formed if every opening bracket ( has a matching closing bracket ) that appears later in the string, and at no prefix do the closing brackets outnumber the opening ones.
The total number of valid strings for a given n is the n-th Catalan number, which grows as roughly 4^n / (n * sqrt(n)). So while the answer set is exponential, it is still much smaller than the 2^(2n) strings you would get by enumerating every binary choice — most of those are invalid and we want to avoid building them in the first place.
A naive brute force generates every string of length 2 * n over the alphabet { '(', ')' } and validates each, costing O(2^(2n) * n). We can do dramatically better with backtracking: maintain running counts of how many ( and ) have been placed and only extend with a character that can still lead to a valid string.
The optimal recursive routine backtrack(open, close, path) adds ( whenever open < n and adds ) whenever close < open (because a closing bracket without a matching opening one is illegal). When path.length == 2 * n we have a complete well-formed string and snapshot it into the results. Time complexity is O(4^n / sqrt(n)) — the size of the answer — and space is O(n) for the recursion stack plus O(n) for the current path.
Examples
n = 3["((()))","(()())","(())()","()(())","()()()"]n = 1["()"]n = 2["(())","()()"]Constraints
- 1 <= n <= 8
- The output may be returned in any order.
- Every returned string has length exactly 2 * n.
- Each string is composed only of the characters '(' and ')'.
- No duplicate strings should appear in the output.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.