Generate Parentheses

🎯

Generate Parentheses

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you are designing a code editor that automatically suggests all valid ways to complete a partially typed expression with parentheses. Generating all valid combinations of parentheses helps ensure syntactically correct expressions.

💡 This problem is a classic example of backtracking where you build solutions incrementally and abandon invalid partial solutions early. Beginners often struggle because they try to generate all sequences blindly without pruning invalid ones, leading to exponential blowup.

📋

Problem Statement

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses strings. Return the list of all valid strings.

1 ≤ n ≤ 8

💡

Example

Input"n = 3"

Output((()))(()())(())()()(())()()()

All valid combinations of 3 pairs of parentheses are generated without duplicates.

• n = 1 → ["()"]
• n = 0 → [] (no pairs means no parentheses)
• n = 2 → ["(())", "()()"]
• n = 8 → large output but must complete efficiently

⚠️

Common Mistakes

Adding ')' when close count equals or exceeds open count

Generates invalid sequences with unbalanced parentheses

✅ Only add ')' if close_count < open_count

Not backtracking properly by forgetting to remove last character

Leads to incorrect sequences or duplicates

✅ Always remove last character after recursive call (pop or deleteCharAt)

Using string concatenation in languages with immutable strings without optimization

Slower performance and higher memory usage

✅ Use mutable string builders or arrays to build strings

Not handling base case correctly (length == 2*n)

May cause infinite recursion or missing results

✅ Check length before adding to results and returning

Trying to generate sequences without pruning invalid states

Exponential time blowup and TLE

✅ Prune by tracking counts and only adding valid parentheses

🧠

Brute Force (Generate All and Check Validity)

💡 This approach exists to build intuition by generating all possible sequences of '(' and ')' and then filtering valid ones. It is simple but inefficient, showing why pruning is necessary.

Intuition

Generate all 2^(2n) sequences of '(' and ')' of length 2n, then check each sequence for validity by ensuring parentheses are balanced.

Algorithm

1. Generate all sequences of length 2n consisting of '(' and ')'.
2. For each sequence, check if it is a valid parentheses string.
3. If valid, add it to the result list.
4. Return the list of valid sequences.

💡 The challenge is understanding how to generate all sequences and then how to validate them, which is straightforward but computationally expensive.

</>

Code

def generateParenthesis(n):
    def is_valid(s):
        balance = 0
        for char in s:
            if char == '(': balance += 1
            else: balance -= 1
            if balance < 0: return False
        return balance == 0

    def backtrack(S):
        if len(S) == 2 * n:
            if is_valid(S):
                result.append(''.join(S))
            return
        S.append('(')
        backtrack(S)
        S.pop()
        S.append(')')
        backtrack(S)
        S.pop()

    result = []
    backtrack([])
    return result

# Example usage
if __name__ == '__main__':
    print(generateParenthesis(3))

Line Notes

def is_valid(s):Defines a helper to check if a sequence is balanced

balance = 0Initialize balance counter to track open and close parentheses

if balance < 0: return FalseEarly exit if closing parenthesis appears before matching opening

if len(S) == 2 * n:Base case: sequence complete

S.append('(')Try adding '(' to the sequence

S.pop()Backtrack by removing last added character

import java.util.*;
public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), n, result);
        return result;
    }

    private static void backtrack(StringBuilder sb, int n, List<String> result) {
        if (sb.length() == 2 * n) {
            if (isValid(sb.toString())) {
                result.add(sb.toString());
            }
            return;
        }
        sb.append('(');
        backtrack(sb, n, result);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(')');
        backtrack(sb, n, result);
        sb.deleteCharAt(sb.length() - 1);
    }

    private static boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}

Line Notes

private static void backtrack(StringBuilder sb, int n, List<String> result)Recursive helper generating all sequences blindly

if (sb.length() == 2 * n)Check if sequence length reached

if (isValid(sb.toString()))Validate the generated sequence

sb.append('(');Add '(' and recurse

sb.deleteCharAt(sb.length() - 1);Backtrack by removing last char

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isValid(const string &s) {
    int balance = 0;
    for (char c : s) {
        if (c == '(') balance++;
        else balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

void backtrack(string &current, int n, vector<string> &result) {
    if (current.size() == 2 * n) {
        if (isValid(current)) {
            result.push_back(current);
        }
        return;
    }
    current.push_back('(');
    backtrack(current, n, result);
    current.pop_back();
    current.push_back(')');
    backtrack(current, n, result);
    current.pop_back();
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    backtrack(current, n, result);
    return result;
}

int main() {
    int n = 3;
    vector<string> res = generateParenthesis(n);
    for (auto &s : res) cout << s << endl;
    return 0;
}

Line Notes

bool isValid(const string &s)Helper to check if parentheses are balanced

if (balance < 0) return false;Early pruning invalid sequences

current.push_back('(');Try adding '('

current.pop_back();Backtrack by removing last character

function generateParenthesis(n) {
    const result = [];
    function isValid(s) {
        let balance = 0;
        for (const char of s) {
            if (char === '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance === 0;
    }
    function backtrack(s) {
        if (s.length === 2 * n) {
            if (isValid(s)) result.push(s);
            return;
        }
        backtrack(s + '(');
        backtrack(s + ')');
    }
    backtrack('');
    return result;
}

console.log(generateParenthesis(3));

Line Notes

function isValid(s)Checks if string s is balanced parentheses

if (balance < 0) return false;Invalid if more ')' than '(' at any point

if (s.length === 2 * n)Base case: full length sequence generated

backtrack(s + '(');Add '(' and recurse

⏱

Complexity

TimeO(2^(2n) * n)

SpaceO(2^(2n) * n)

There are 2^(2n) sequences of length 2n, each checked for validity in O(n) time.

💡 For n=3, this means checking 2^6=64 sequences, each up to length 6, which is manageable but grows exponentially.

Interview Verdict: TLE for large n / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem and motivates pruning.

🧠

Backtracking with Pruning (Count Open and Close)

💡 This approach improves efficiency by pruning invalid sequences early, only adding '(' if we still have some left, and ')' only if it won't unbalance the string.

Intuition

Build the string step-by-step, keeping track of how many '(' and ')' have been used. Only add '(' if we still have some left, and add ')' only if it won't lead to invalid sequence (i.e., close count < open count).

Algorithm

1. Start with an empty string and counts of open and close parentheses used.
2. If the string length is 2n, add it to results.
3. If open count < n, add '(' and recurse.
4. If close count < open count, add ')' and recurse.

💡 The key insight is pruning invalid sequences early by tracking counts, which drastically reduces the search space.

</>

Code

def generateParenthesis(n):
    result = []
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)
    backtrack('', 0, 0)
    return result

# Example usage
if __name__ == '__main__':
    print(generateParenthesis(3))

Line Notes

def backtrack(s, open_count, close_count):Recursive helper tracking counts and current string

if len(s) == 2 * n:Base case: full valid sequence generated

if open_count < n:Add '(' if we still have some left

if close_count < open_count:Add ')' only if it won't unbalance

import java.util.*;
public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack("", 0, 0, n, result);
        return result;
    }

    private static void backtrack(String current, int open, int close, int max, List<String> result) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        if (open < max) backtrack(current + "(", open + 1, close, max, result);
        if (close < open) backtrack(current + ")", open, close + 1, max, result);
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}

Line Notes

private static void backtrack(String current, int open, int close, int max, List<String> result)Helper with current string and counts

if (current.length() == max * 2)Base case: full valid sequence

if (open < max)Add '(' if possible

if (close < open)Add ')' only if valid

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void backtrack(string current, int open, int close, int max, vector<string> &result) {
    if (current.size() == 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() {
    int n = 3;
    vector<string> res = generateParenthesis(n);
    for (auto &s : res) cout << s << endl;
    return 0;
}

Line Notes

void backtrack(string current, int open, int close, int max, vector<string> &result)Recursive helper with counts and current string

if (current.size() == max * 2)Base case: full valid sequence

if (open < max)Add '(' if available

if (close < open)Add ')' only if valid

function generateParenthesis(n) {
    const result = [];
    function backtrack(s, open, close) {
        if (s.length === 2 * n) {
            result.push(s);
            return;
        }
        if (open < n) backtrack(s + '(', open + 1, close);
        if (close < open) backtrack(s + ')', open, close + 1);
    }
    backtrack('', 0, 0);
    return result;
}

console.log(generateParenthesis(3));

Line Notes

function backtrack(s, open, close)Helper tracking current string and counts

if (s.length === 2 * n)Base case: full valid sequence

if (open < n)Add '(' if possible

if (close < open)Add ')' only if valid

⏱

Complexity

TimeO(4^n / sqrt(n))

SpaceO(4^n / sqrt(n))

Number of valid sequences is the nth Catalan number ~4^n / (n^(3/2)), and each sequence is length 2n.

💡 For n=3, this means about 5 sequences generated efficiently, much fewer than brute force.

Interview Verdict: Accepted / Standard solution to code in interviews

This is the canonical backtracking solution that balances clarity and efficiency.

🧠

Backtracking with StringBuilder / Mutable String (Language-Specific Optimization)

💡 This approach is a minor optimization that uses mutable string structures to avoid string concatenation overhead, improving performance in languages like Java and C++.

Intuition

Instead of creating new strings on each recursion, use a mutable string builder to append and remove characters, reducing memory allocations.

Algorithm

1. Use a mutable string builder to build the current sequence.
2. Append '(' or ')' as allowed and recurse.
3. Remove last character after recursion to backtrack.
4. Add complete sequences to result list.

💡 The logic is the same as standard backtracking, but string operations are optimized.

</>

Code

def generateParenthesis(n):
    result = []
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(''.join(s))
            return
        if open_count < n:
            s.append('(')
            backtrack(s, open_count + 1, close_count)
            s.pop()
        if close_count < open_count:
            s.append(')')
            backtrack(s, open_count, close_count + 1)
            s.pop()
    backtrack([], 0, 0)
    return result

if __name__ == '__main__':
    print(generateParenthesis(3))

Line Notes

def backtrack(s, open_count, close_count):Use list as mutable string builder

if len(s) == 2 * n:Base case: full valid sequence generated

result.append(''.join(s))Join list into string when complete

s.append('(')Append '(' to builder

s.pop()Remove last char to backtrack

import java.util.*;
public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), 0, 0, n, result);
        return result;
    }

    private static void backtrack(StringBuilder sb, int open, int close, int max, List<String> result) {
        if (sb.length() == max * 2) {
            result.add(sb.toString());
            return;
        }
        if (open < max) {
            sb.append('(');
            backtrack(sb, open + 1, close, max, result);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            backtrack(sb, open, close + 1, max, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }
}

Line Notes

StringBuilder sbMutable string builder to avoid string concatenation overhead

if (sb.length() == max * 2)Base case: full valid sequence generated

sb.append('(');Add '(' efficiently

sb.deleteCharAt(sb.length() - 1);Backtrack by removing last char

result.add(sb.toString());Add complete string to results

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void backtrack(string &current, int open, int close, int max, vector<string> &result) {
    if (current.size() == max * 2) {
        result.push_back(current);
        return;
    }
    if (open < max) {
        current.push_back('(');
        backtrack(current, open + 1, close, max, result);
        current.pop_back();
    }
    if (close < open) {
        current.push_back(')');
        backtrack(current, open, close + 1, max, result);
        current.pop_back();
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    backtrack(current, 0, 0, n, result);
    return result;
}

int main() {
    int n = 3;
    vector<string> res = generateParenthesis(n);
    for (auto &s : res) cout << s << endl;
    return 0;
}

Line Notes

string &currentMutable string reference to avoid copies

if (current.size() == max * 2)Base case: full valid sequence generated

current.push_back('(');Add '(' efficiently

current.pop_back();Backtrack by removing last char

result.push_back(current);Add complete string to results

function generateParenthesis(n) {
    const result = [];
    const sb = [];
    function backtrack(open, close) {
        if (sb.length === 2 * n) {
            result.push(sb.join(''));
            return;
        }
        if (open < n) {
            sb.push('(');
            backtrack(open + 1, close);
            sb.pop();
        }
        if (close < open) {
            sb.push(')');
            backtrack(open, close + 1);
            sb.pop();
        }
    }
    backtrack(0, 0);
    return result;
}

console.log(generateParenthesis(3));

Line Notes

const sb = [];Use array as mutable string builder

if (sb.length === 2 * n)Base case: full valid sequence generated

sb.push('(');Add '(' efficiently

sb.pop();Backtrack by removing last char

result.push(sb.join(''));Join array into string when complete

⏱

Complexity

TimeO(4^n / sqrt(n))

SpaceO(4^n / sqrt(n))

Same as standard backtracking but with less overhead from string concatenation.

💡 This optimization matters for larger n where string concatenation cost adds up.

Interview Verdict: Accepted / Recommended for performance-sensitive languages

This is a practical optimization that interviewers appreciate but is not required for correctness.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the backtracking with pruning approach (Approach 2). Approach 1 is useful to mention for understanding, and Approach 3 is a minor optimization.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(2n) * n)	O(2^(2n) * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Pruning	O(4^n / sqrt(n))	O(4^n / sqrt(n))	Yes (deep recursion)	Yes	Code this approach
3. Backtracking with Mutable String	O(4^n / sqrt(n))	O(4^n / sqrt(n))	Yes (deep recursion)	Yes	Mention as optimization if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimized backtracking solution.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach to generate all sequences and validate them.Explain why brute force is inefficient and introduce pruning with counts.Write the backtracking code with pruning.Test with sample inputs and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning invalid states early, and your ability to write clean recursive code with correct base cases.

Common Follow-ups

• What if we want to generate only the count of valid sequences? → Use Catalan number formula or DP.
• Can you generate sequences iteratively? → Yes, but more complex; backtracking is preferred.

💡 Follow-ups test your knowledge of combinatorics and alternative approaches beyond recursion.

🔍

Pattern Recognition

When to Use

1) Problem asks for all valid combinations of balanced parentheses or brackets. 2) Constraints require generating all sequences, not just counting. 3) Problem involves building strings with balanced open/close pairs. 4) Backtracking or DFS with pruning is a natural fit.

Signature Phrases

generate all combinationswell-formed parenthesesbalanced parentheses

NOT This Pattern When

Counting valid parentheses without generating sequences is a DP or combinatorics problem, not backtracking.

Similar Problems

Valid Parentheses - checks if a string is balancedRemove Invalid Parentheses - generate valid strings by removing minimum invalid parentheses

Practice

1. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting

2. The following BFS code attempts to remove invalid parentheses but contains a subtle bug:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                # BUG: removing characters other than parentheses
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

What is the bug in this code?

medium

A. The found flag is reset inside the inner loop, causing premature termination

B. The is_valid function incorrectly returns True for unbalanced strings

C. The visited set is not updated correctly, causing duplicates

D. The code removes characters even if they are not '(' or ')', expanding search unnecessarily

Solution

1. Step 1: Identify character removal condition

   The code removes characters at every index without checking if they are '(' or ')', which is incorrect.

2. Step 2: Consequence of bug

   Removing non-parenthesis characters leads to invalid strings and unnecessary BFS states, increasing complexity and possibly missing valid results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only parentheses should be removed to prune search space [OK]

Hint: Only remove '(' or ')' characters during BFS [OK]

Common Mistakes:

• Removing all characters
• Incorrect visited updates
• Misusing found flag

3. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily

4. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order