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. Consider the following Python code implementing the bitmask backtracking solution for N-Queens II. What is the final return value of totalNQueens(4)?

easy

A. 2

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace initial call for n=4

   Start with row=0, no columns or diagonals occupied, all 4 columns available.

2. Step 2: Count valid placements recursively

   Backtracking explores all valid queen placements; for n=4, there are exactly 2 distinct solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known result for 4-queens is 2 solutions [OK]

Hint: 4-queens has 2 solutions; bitmask backtracking counts all [OK]

Common Mistakes:

• Off-by-one counting
• Confusing number of solutions with board size

2. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

3. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

4. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

5. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.