Generate Parentheses solution and explanation
Google
9 more videos on this problem
Generate Parentheses - Stack - Leetcode 22NeetCode · 13:37 · 554K views
LeetCode 22. Generate ParenthesesNick White · 12:39 · 89K views
Leetcode 22. Generate Parentheses ||Code+ Explanation + Full recursion flow Walkthrough ||June DailyCode with Alisha · 18:02 · 34K views
Generate Parentheses - Leetcode 22 - Recursive Backtracking (Python)Greg Hogg · 9:43 · 21K views
LC#1 🔥 Generate Parentheses - LeetCode 22 | Intuition + Code | Recursion Tree | Backtracking | JavaInterviewWithBunny · 24:25 · 11K views
Generate Parentheses - LeetCode 22 - Python #backtracking #recursion #leetcodeDeepti Talesra · 15:03 · 2K views
22. Generate Parentheses | Backtracking Series | LEETCODEcode Explainer · 10:30 · 2K views
Generate Parentheses | LeetCode 22 BacktrackingDestination FAANG · 16:03 · 1K views
22. Generate Parentheses 括号生成【LeetCode 力扣题解】LeetCode 力扣 · 5:21 · 1K views
22. Generate Parentheses Leetcode Problem | Solution with Explanation | DSA Problem SeriesCoding Blocks · 7:27 · 1K views
The problem
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 <= 8
Approach overview
Problem 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.
Approach 1: Backtracking Approach
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.
def generateParenthesis(n):
def backtrack(S = '', left = 0, right = 0):
if len(S) == 2 * n:
result.append(S)
return
if left < n:
backtrack(S + '(', left + 1, right)
if right < left:
backtrack(S + ')', left, right + 1)
result = []
backtrack()
return result
# Example Usage
print(generateParenthesis(3))import java.util.ArrayList;
import java.util.List;
public class GenerateParentheses {
public static List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
private static void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) {
result.add(current);
return;
}
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}
public static void main(String[] args) {
List<String> parentheses = generateParenthesis(3);
for (String s : parentheses) {
System.out.println(s);
}
}
}#include <iostream>
#include <vector>
using namespace std;
void backtrack(string current, int open, int close, int max, vector<string> &result) {
if (current.length() == max * 2) {
result.push_back(current);
return;
}
if (open < max) {
backtrack(current + "(", open + 1, close, max, result);
}
if (close < open) {
backtrack(current + ")", open, close + 1, max, result);
}
}
vector<string> generateParenthesis(int n) {
vector<string> result;
backtrack("", 0, 0, n, result);
return result;
}
int main() {
vector<string> parentheses = generateParenthesis(3);
for (const string &s : parentheses) {
cout << s << endl;
}
return 0;
}function generateParenthesis(n) {
const result = [];
function backtrack(current = '', open = 0, close = 0) {
if (current.length === n * 2) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack();
return result;
}
// Example usage:
console.log(generateParenthesis(3));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void generate(char *current, int open, int close, int max, char ***result, int *size) {
if (strlen(current) == max * 2) {
(*result)[*size] = strdup(current);
(*size)++;
return;
}
if (open < max) {
strcat(current, "(");
generate(current, open + 1, close, max, result, size);
current[strlen(current) - 1] = '\0';
}
if (close < open) {
strcat(current, ")");
generate(current, open, close + 1, max, result, size);
current[strlen(current) - 1] = '\0';
}
}
char **generateParenthesis(int n, int *returnSize) {
char **result = (char **)malloc(sizeof(char *) * 1000);
*returnSize = 0;
char current[2 * n + 1];
current[0] = '\0';
generate(current, 0, 0, n, &result, returnSize);
return result;
}
int main() {
int size;
char **parentheses = generateParenthesis(3, &size);
for (int i = 0; i < size; i++) {
printf("%s\n", parentheses[i]);
free(parentheses[i]);
}
free(parentheses);
return 0;
}using System;
using System.Collections.Generic;
class GenerateParentheses {
public static IList<string> GenerateParenthesis(int n) {
List<string> result = new List<string>();
Backtrack(result, "", 0, 0, n);
return result;
}
private static void Backtrack(List<string> result, string current, int open, int close, int max) {
if (current.Length == max * 2) {
result.Add(current);
return;
}
if (open < max) {
Backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
Backtrack(result, current + ")", open, close + 1, max);
}
}
static void Main() {
IList<string> parentheses = GenerateParenthesis(3);
foreach (string s in parentheses) {
Console.WriteLine(s);
}
}
}In Python, the function uses a helper function 'backtrack' that takes the current string and counts of left and right parentheses. The recursive logic ensures that any partially constructed string is valid by allowing adding a '(' if the left count hasn't reached 'n', and a ')' if '(' count is greater than ')'. The function is simple yet effectively searches through the possibilities.
Time Complexity: O(4^n/sqrt(n)), reflecting the growth of Catalan numbers.
Space Complexity: O(n), which accounts for the maximum depth of the recursion stack.
Approach 2: DFS + Pruning
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:
- If
l \gt norr \gt norl \lt r, then the current bracket combinationtis invalid, return directly; - If
l = nandr = n, then the current bracket combinationtis valid, add it to the answer arrayans, and return directly; - We can choose to add a left bracket, and recursively execute
dfs(l + 1, r, t + "("); - We can also choose to add a right bracket, and recursively execute
dfs(l, r + 1, t + ")").
The time complexity is O(2^{ntimes 2} times n), and the space complexity is O(n).
function generateParenthesis(n: number): string[] {
function dfs(l, r, t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.push(t);
return;
}
dfs(l + 1, r, t + '(');
dfs(l, r + 1, t + ')');
}
let ans = [];
dfs(0, 0, '');
return ans;
}func generateParenthesis(n int) (ans []string) {
var dfs func(int, int, string)
dfs = func(l, r int, t string) {
if l > n || r > n || l < r {
return
}
if l == n && r == n {
ans = append(ans, t)
return
}
dfs(l+1, r, t+"(")
dfs(l, r+1, t+")")
}
dfs(0, 0, "")
return ans
}impl Solution {
fn dfs(left: i32, right: i32, s: &mut String, res: &mut Vec<String>) {
if left == 0 && right == 0 {
res.push(s.clone());
return;
}
if left > 0 {
s.push('(');
Self::dfs(left - 1, right, s, res);
s.pop();
}
if right > left {
s.push(')');
Self::dfs(left, right - 1, s, res);
s.pop();
}
}
pub fn generate_parenthesis(n: i32) -> Vec<String> {
let mut res = Vec::new();
Self::dfs(n, n, &mut String::new(), &mut res);
res
}
}class Solution {
/**
* @param Integer $n
* @return String[]
*/
function generateParenthesis($n) {
$ans = [];
$dfs = function ($l, $r, $t) use ($n, &$ans, &$dfs) {
if ($l > $n || $r > $n || $l < $r) {
return;
}
if ($l == $n && $r == $n) {
$ans[] = $t;
return;
}
$dfs($l + 1, $r, $t . '(');
$dfs($l, $r + 1, $t . ')');
};
$dfs(0, 0, '');
return $ans;
}
}Approach 3: Recursion
function generateParenthesis(n: number): string[] {
if (n === 1) return ['()'];
return [
...new Set(
generateParenthesis(n - 1).flatMap(s =>
Array.from(s, (_, i) => s.slice(0, i) + '()' + s.slice(i)),
),
),
];
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(4^n/sqrt(n)), reflecting the growth of Catalan numbers. |
| DFS + Pruning | – |
| Recursion | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Generate Parentheses easy or hard?
Generate Parentheses is typically classified as a medium difficulty problem. The challenge comes from recognizing that you should prune invalid states during generation rather than checking validity afterward. Once the backtracking constraint is clear, the implementation becomes straightforward.
How to solve Generate Parentheses in O(n)?
Generating all valid parentheses combinations cannot be done in O(n) time because the output size itself grows exponentially. The optimal approach generates exactly the valid sequences using backtracking with pruning, which runs in O(Cn) time where Cn is the Catalan number.
What is the best approach for Generate Parentheses?
Backtracking with pruning is the standard solution. Build the string step by step while tracking how many opening and closing parentheses have been used. Only add a closing parenthesis when it does not exceed the number of openings. This avoids generating invalid sequences and produces exactly the Catalan number of valid results.
Is Generate Parentheses asked at Google/Amazon/Meta?
Generate Parentheses is a common interview problem at major tech companies including Google, Amazon, Meta, and Microsoft. It tests recursion, backtracking, and understanding of constrained combinatorial generation, which frequently appears in coding interviews.
What data structure is used in Generate Parentheses?
Most implementations use recursion with a mutable string builder or array to construct the sequence. Conceptually it relies on backtracking and the call stack rather than a complex data structure. Some validation approaches also use a stack to check correctness of parentheses.
What is the time complexity of Generate Parentheses?
The optimal backtracking solution runs in O(Cn) time, where Cn is the nth Catalan number. This is approximately O(4^n / √n). Each valid combination of length 2n must be generated once, and recursion depth requires O(n) auxiliary space.
Generate Parentheses Python or Java solution approach
In both Python and Java, the common approach uses recursive backtracking. Track the count of opening and closing parentheses and append characters while maintaining validity rules. The recursion stops when the string length reaches 2n and the combination is added to the result list.