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. You need to count the number of permutations of numbers from 1 to n such that for each position i, either the number at position i is divisible by i or i is divisible by the number. Which algorithmic approach best guarantees an efficient solution?

easy

A. Sorting numbers and checking divisibility in a single pass

B. Greedy algorithm that places numbers based on divisibility from left to right

C. Dynamic programming with memoization over subsets

D. Backtracking with pruning to explore valid permutations only

Solution

1. Step 1: Understand problem constraints

   The problem requires counting permutations with divisibility conditions at each position, which is a combinatorial search problem.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning efficiently explores only valid permutations, avoiding full enumeration, unlike greedy or sorting approaches which fail to guarantee correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid branches early, ensuring correctness and efficiency [OK]

Hint: Backtracking prunes invalid permutations early [OK]

Common Mistakes:

• Assuming greedy can solve divisibility constraints
• Thinking sorting suffices for permutation constraints

2. Given the following code snippet, what is the final output of letterCombinations('23')?

from collections import deque

def letterCombinations(digits):
    if not digits:
        return []
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

print(letterCombinations('23'))

easy

A. ['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']

B. ['abc', 'def']

C. ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

D. ['a', 'b', 'c', 'd', 'e', 'f']

Solution

1. Step 1: Trace queue after processing digit '2'

   Initial queue: [''] Letters for '2': 'abc' After processing: ['a', 'b', 'c']

2. Step 2: Trace queue after processing digit '3'

   Letters for '3': 'def' For each prefix in ['a', 'b', 'c'], append each letter: 'a' + 'd','e','f' -> 'ad','ae','af' 'b' + 'd','e','f' -> 'bd','be','bf' 'c' + 'd','e','f' -> 'cd','ce','cf' Final queue: ['ad','ae','af','bd','be','bf','cd','ce','cf']

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected letter combinations for '23' [OK]

Hint: Queue expands combinations breadth-first per digit [OK]

Common Mistakes:

• Mixing order of combinations
• Confusing concatenation order

3. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

Solution:

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

4. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            # Bug: Missing check for leading zeros
            if length == 3 and int(segment) > 255:
                continue
            stack.append((start + length, path + [segment]))
    return res

medium

A. Line missing check for segments with leading zeros

B. Line checking if segment length is 3 and value > 255

C. Line pruning based on remaining characters and segments

D. Line appending new segment to stack

Solution

1. Step 1: Identify missing validation

   The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.

2. Step 2: Confirm other checks are correct

   Check for segment > 255 and pruning are present and correct; appending to stack is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check allows invalid IP segments [OK]

Hint: Leading zero check is mandatory to avoid invalid IPs [OK]

Common Mistakes:

• Forgetting leading zero validation
• Misplacing pruning conditions

5. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?

def backtrack():
    if not empties:
        return True
    empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
    r, c = empties[0]
    for ch in get_candidates(r, c):
        board[r][c] = ch
        rows[r].add(ch)
        cols[c].add(ch)
        boxes[(r//3)*3 + c//3].add(ch)
        empties.pop(0)
        if backtrack():
            return True
        # Undo changes
        board[r][c] = '.'
        rows[r].remove(ch)
        cols[c].remove(ch)
        boxes[(r//3)*3 + c//3].remove(ch)
        empties.insert(0, (r, c))
    return False

medium

A. Line that pops the first empty cell from empties

B. Line that sorts empties by candidate count

C. Line that adds ch to rows[r]

D. Line that resets board[r][c] to '.' after backtracking

Solution

Solution:

1. Step 1: Identify mutation of empties list

   The line popping empties[0] removes the cell but is never restored on backtrack failure.

2. Step 2: Consequence of missing restoration

   Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking requires undoing all changes including empties list [OK]

Hint: Backtracking must undo all state changes, including empties list [OK]

Common Mistakes:

• Forgetting to restore empties after pop
• Assuming board reset is sufficient