Log inSign up
mediumLeetCodeNot Started

Generate Parentheses

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Given n pairs of parentheses, write a function to *generate all combinations of well-formed parentheses*.

Example 1 · 3 Pairs of Parentheses:

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation: All 5 well-formed combinations for n = 3.

Example 2 · 1 Pair of Parentheses:

Input: n = 1
Output: ["()"]
Explanation: Only 1 valid combination exists.

Constraints:

  • 1 <= n <= 8

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master state-bounded string generation where prefix constraints guarantee validity.
  • Understand the combinatorial origin and formula of the Catalan numbers.
  • Implement zero-waste backtracking where invalid prefixes are pruned before being generated.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generate all well-formed or valid parenthesis sequences of length 2*n
  • Dynamic validity constraints dependent on prefix counts
  • Output count follows Catalan numbers C_n

Algorithmic Decision Tree:

  • If open < n, append ( and recurse backtrack(open + 1, close).
  • If close < open, append ) and recurse backtrack(open, close + 1).
  • If open == n && close == n, capture solution.

Connected Patterns:

Valid ParenthesesRemove Invalid ParenthesesScore of Parentheses

1. Generate All 2^(2N) Sequences + Validator

Intuition

Recursively build all 2^(2N) binary strings of length 2N. For each complete string, check if it is valid: balance must never drop below 0 and must finish at 0.

When to apply: Baseline comparison to illustrate the exponential difference between generating everything vs guided pruning.

Algorithm

  1. Recursively generate all 2^(2N) strings.
  2. Check validity: iterate chars, increment for (, decrement for ). If balance < 0, invalid. If final balance == 0, valid.
  3. Collect all valid strings into result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 bool isValid(const string& s) {
9 int bal = 0;
10 for (char c : s) {
11 if (c == '(') bal++;
12 else bal--;
13 if (bal < 0) return false;
14 }
15 return bal == 0;
16 }
17
18 void generateAll(string current, int n, vector<string>& result) {
19 if (current.length() == 2 * n) {
20 if (isValid(current)) result.push_back(current);
21 return;
22 }
23 generateAll(current + '(', n, result);
24 generateAll(current + ')', n, result);
25 }
26
27public:
28 vector<string> generateParenthesis(int n) {
29 vector<string> result;
30 generateAll("", n, result);
31 return result;
32 }
33};
34
35int main() {
36 Solution sol;
37 auto res = sol.generateParenthesis(3);
38 for (const string& s : res) cout << s << " ";
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(2^(2N) * N) — Generates 2^(2N) strings, each verified in O(N) time.
  • Space complexity: O(N) — Recursion depth is 2N.

2. Divide and Conquer (Closure Form / Dynamic Programming)

Intuition

Every valid parenthesis sequence can be uniquely represented as ( + left + ) + right, where left has c pairs and right has n - 1 - c pairs for c from 0 to n - 1.

When to apply: When exploring the inductive mathematical decomposition of Catalan sequences.

Algorithm

  1. Base case: dp[0] = [''].
  2. For i from 1 to n:
  3. - For c from 0 to i - 1:
  4. - For each left in dp[c] and right in dp[i - 1 - c]:
  5. - Add (' + left + ')' + right to dp[i].
  6. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<string> generateParenthesis(int n) {
10 vector<vector<string>> dp(n + 1);
11 dp[0] = {""};
12
13 for (int i = 1; i <= n; i++) {
14 for (int c = 0; c < i; c++) {
15 for (const string& left : dp[c]) {
16 for (const string& right : dp[i - 1 - c]) {
17 dp[i].push_back("(" + left + ")" + right);
18 }
19 }
20 }
21 }
22 return dp[n];
23 }
24};
25
26int main() {
27 Solution sol;
28 auto res = sol.generateParenthesis(3);
29 for (const string& s : res) cout << s << " ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(C_N * N) — Generates all Catalan combinations without visiting invalid strings.
  • Space complexity: O(C_N * N) — DP table stores intermediate combination lists.

3. Guided Backtracking with Open/Close Invariant (Optimal)

Intuition

By enforcing open < n for placing ( and close < open for placing ), the recursion only explores valid prefixes. Every leaf reached is guaranteed to be a valid well-formed parenthesis combination.

When to apply: The classic, industry-standard interview solution.

Algorithm

  1. Define backtrack(open, close, current):
  2. - If current.length == 2 * n, append current to result and return.
  3. - If open < n: recurse backtrack(open + 1, close, current + '(').
  4. - If close < open: recurse backtrack(open, close + 1, current + ')').
  5. Start with backtrack(0, 0, '').

Guided Parenthesis Tree Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Start at root: open = 0, close = 0, path = ''
Visual state
Values and pointers at this exact step
tree
Root
o:0, c:0, path: ''

Node order shown; add connections to display explicit tree edges.

Variables at this step
open
0
close
0
path
Why this step matters

Start at root: open = 0, close = 0, path = ''. Can only add ( (open < 2).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void backtrack(int open, int close, int n, string& current, vector<string>& result) {
9 if (current.length() == 2 * n) {
10 result.push_back(current);
11 return;
12 }
13
14 if (open < n) {
15 current.push_back('(');
16 backtrack(open + 1, close, n, current, result);
17 current.pop_back(); // backtrack
18 }
19
20 if (close < open) {
21 current.push_back(')');
22 backtrack(open, close + 1, n, current, result);
23 current.pop_back(); // backtrack
24 }
25 }
26
27public:
28 vector<string> generateParenthesis(int n) {
29 vector<string> result;
30 string current;
31 backtrack(0, 0, n, current, result);
32 return result;
33 }
34};
35
36int main() {
37 Solution sol;
38 auto res = sol.generateParenthesis(3);
39 for (const string& s : res) cout << s << " ";
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(4^N / sqrt(N)) — Generates exactly the N-th Catalan number C_N = (1 / (N+1)) * C(2N, N) ~ 4N / (N^(1.5) * sqrt(pi)) valid strings.
  • Space complexity: O(N) — Maximum recursion stack depth is 2N.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate All 2^(2N) SequencesO(2^(2N) * N)O(N)Generate all binary strings and test validity at leaves.Invalid subtree exploration
2.Divide and Conquer (Closure Form)O(C_N * N)O(C_N * N)Dynamic programming using (left)right closure property.DP string concatenation memory
3.Guided Backtracking with Open/Close InvariantOptimalO(4^N / sqrt(N))O(N)Place ( when open < n and ) when close < open.Catalan combination count

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using close < n instead of close < open for placing ) (which allows invalid prefixes like )() to be generated).

Pitfall 2:

Forgetting to backtrack (pop character) when using a shared mutable string/list.

Crucial Edge Cases to Validate:

  • n = 1: returns [()].
  • n = 2: returns [(()), ()()].
  • Maximum n = 8: returns 1430 valid combinations within milliseconds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the Catalan number asymptotic complexity O(4N / N^(1.5)) directly.
  2. Explain the two crisp placement rules (open < n and close < open) before writing code.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the condition close < open guarantee that no prefix has unbalanced closing parentheses?

2.How many valid parenthesis strings exist for n = 4?

Back to DSA Sheet