Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8Problem Overview: Generate all valid combinations of n pairs of parentheses. A valid sequence means every opening bracket ( is matched with a closing bracket ) in the correct order.
Approach 1: Brute Force Enumeration (O(2^(2n)) time, O(2n) space)
The naive idea generates every possible string of length 2n consisting of ( and ). After generating each candidate, you validate whether it forms a correct parentheses sequence using a counter or stack. Validation takes O(n), and the total candidates are 2^(2n). Most generated strings are invalid, so the algorithm wastes significant work. This approach helps you understand the constraint structure but is not practical for larger n.
Approach 2: Backtracking with Validity Pruning (O(Cn) time, O(n) space)
This is the standard solution used in interviews. Instead of generating all strings, build the sequence incrementally using backtracking. Track two counters: how many opening parentheses and closing parentheses have been used. Add ( if the number of opens is less than n. Add ) only when the number of closes is less than the number of opens. This pruning ensures every partial string remains valid, eliminating invalid branches early. The number of valid results equals the Catalan number Cn, so the time complexity becomes O(Cn), approximately O(4^n / √n), and recursion depth requires O(n) space.
Approach 3: Dynamic Programming using Catalan Construction (O(Cn * n) time, O(Cn) space)
You can also build solutions using dynamic programming. Let dp[i] represent all valid parentheses combinations using i pairs. For each split i, treat one pair as the outer wrapper and combine results from smaller subproblems: ( left ) right, where left comes from dp[j] and right from dp[i-1-j]. This mirrors the Catalan recurrence. The DP approach clearly shows the mathematical structure but requires storing all intermediate results, which increases memory usage compared to recursive generation.
Strings are built character by character, so operations involve simple append and backtrack steps on a mutable buffer or string builder. The recursion tree is heavily pruned because invalid states (more closing than opening parentheses) are never explored. Problems like this commonly appear in string generation and combinatorial search tasks.
Recommended for interviews: Backtracking with pruning. It directly models the constraint that closing brackets cannot exceed opening brackets. Interviewers expect you to recognize the Catalan structure and construct valid sequences incrementally. Mentioning the brute force idea shows you understand the search space, but implementing the pruned backtracking solution demonstrates stronger algorithmic reasoning.
The key idea here is to build the solution by choosing either an opening or a closing parenthesis at each step. We make sure that any partial solution is valid - at any point in time, the number of closing parentheses cannot exceed the number of opening ones. We also stop adding parentheses when we have used 'n' of each.
This solution uses backtracking to generate all valid combinations of parentheses. Start with an empty string, and use two counters: 'open' and 'close'. As long as 'open' is less than 'n', add an opening parenthesis. As long as 'close' is less than 'open', add a closing parenthesis. When the length of the current string is 2 * n, it's added to the result. Each combination is built step-by-step, exploring possibilities and backtracking if needed.
Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth.
Space Complexity: O(n) for recursion stack.
The range of n in the problem is [1, 8], so we can directly solve this problem through "brute force search + pruning".
We design a function dfs(l, r, t), where l and r represent the number of left and right brackets respectively, and t represents the current bracket sequence. Then we can get the following recursive structure:
l \gt n or r \gt n or l \lt r, then the current bracket combination t is invalid, return directly;l = n and r = n, then the current bracket combination t is valid, add it to the answer array ans, and return directly;dfs(l + 1, r, t + "(");dfs(l, r + 1, t + ")").The time complexity is O(2^{ntimes 2} times n), and the space complexity is O(n).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth. |
| DFS + Pruning | — |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^(2n) * n) | O(n) | Conceptual baseline to understand the search space of all possible strings |
| Backtracking with Pruning | O(Cn) ≈ O(4^n / √n) | O(n) | Best practical solution for interviews and coding platforms |
| Dynamic Programming (Catalan Build) | O(Cn * n) | O(Cn) | Useful for understanding Catalan relationships and building solutions bottom‑up |
Generate Parentheses - Stack - Leetcode 22 • NeetCode • 538,794 views views
Watch 9 more video solutions →Practice Generate Parentheses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor