Generate Parentheses

📋

Problem

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.

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

Edge cases: n = 1 → ["()"]n = 0 → [] (no pairs means no parentheses)n = 2 → ["(())", "()()"]

</>

IDE

def generateParenthesis(n: int) -> list:public List<String> generateParenthesis(int n)vector<string> generateParenthesis(int n)function generateParenthesis(n)

def generateParenthesis(n):
    # Write your solution here
    pass

class Solution {
    public List<String> generateParenthesis(int n) {
        // Write your solution here
        return new ArrayList<>();
    }
}

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

vector<string> generateParenthesis(int n) {
    // Write your solution here
    return {};
}

function generateParenthesis(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ((()))(()())(())()()(())Missing last valid sequence '()()()' due to greedy always adding '(' first.✅ In backtracking, explore adding ')' when close < open, not just '(' when open < n.

Wrong: ()()()()()((()))Output includes invalid sequences with more than n pairs due to reusing pairs multiple times.✅ Limit open and close counts to n; do not reuse pairs beyond n.

Wrong: ((()))(()())(())()()(())()()()()Including sequences shorter than 2*n length due to incorrect recursion termination.✅ Add sequences only when length == 2*n.

Wrong: ()Non-empty output for n=0 due to missing base case handling.✅ Return empty list immediately if n=0.

✓

Test Cases

Focus on handling base cases and small inputs correctly before tackling edge cases.

Understand common pitfalls like greedy approaches and off-by-one errors in recursion.

Optimize your backtracking with pruning to handle the largest inputs efficiently.

t1_01basic

Input{"n":3}

Expected["((()))","(()())","(())()","()(())","()()()"]

⏱ Performance - must finish in 2000ms

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

💡 Think about placing '(' and ')' while keeping track of counts.

💡 Use backtracking with counts of open and close parentheses to prune invalid sequences.

💡 Add '(' if open count < n, add ')' if close count < open count.

Why it failed: Output missing or extra strings due to incorrect pruning or validation. Fix by enforcing open < n and close < open conditions strictly.

✓ Correctly generates all valid parentheses combinations for n=3.

t1_02basic

Input{"n":2}

Expected["(())","()()"]

⏱ Performance - must finish in 2000ms

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

💡 Try enumerating all sequences of length 4 with balanced parentheses.

💡 Backtracking with pruning avoids invalid sequences early.

💡 Ensure you only add ')' when close count < open count.

Why it failed: Incorrect output due to allowing ')' when close count >= open count. Fix by adding ')' only if close < open.

✓ Correctly generates all valid parentheses combinations for n=2.

t2_01edge

Input{"n":0}

Expected[""]

⏱ Performance - must finish in 2000ms

No pairs means no parentheses; output is empty list.

💡 Consider what the output should be when n=0.

💡 Check if your code handles zero input without errors.

💡 Return empty list immediately if n=0.

Why it failed: Output non-empty or error for n=0 due to missing base case. Fix by returning [] when n=0.

✓ Correctly returns empty list for n=0.

t2_02edge

Input{"n":1}

Expected["()"]

⏱ Performance - must finish in 2000ms

Single pair of parentheses has only one valid combination.

💡 Smallest non-zero input tests minimal recursion.

💡 Check if your code handles n=1 correctly.

💡 Output should be ['()'] exactly.

Why it failed: Incorrect output for n=1 due to off-by-one or missing base case. Fix by ensuring recursion stops at length 2*n.

✓ Correctly generates ['()'] for n=1.

t2_03edge

Input{"n":8}

Expectednull

⏱ Performance - must finish in 2000ms

Largest input within constraints; must complete efficiently without timeout.

💡 Backtracking with pruning is necessary for large n.

💡 Avoid generating all sequences and then filtering.

💡 Use counts of open and close parentheses to prune early.

Why it failed: Timeout due to brute force or inefficient pruning. Fix by pruning invalid sequences during generation.

✓ Efficiently completes for n=8 using pruning backtracking.

t3_01corner

Input{"n":3}

Expected["((()))","(()())","(())()","()(())","()()()"]

⏱ Performance - must finish in 2000ms

Tests greedy approach trap: adding '(' whenever possible leads to missing valid sequences.

💡 Greedy approach may fail to generate all sequences.

💡 Backtracking must explore both adding '(' and ')' when valid.

💡 Do not always add '(' first; consider adding ')' when allowed.

Why it failed: Missing sequences due to greedy always adding '(' first. Fix by exploring both '(' and ')' branches when valid.

✓ Backtracking explores all valid branches, avoiding greedy trap.

t3_02corner

Input{"n":2}

Expected["(())","()()"]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and this problem: cannot reuse parentheses pairs multiple times.

💡 Each '(' and ')' can only be used once per pair.

💡 Do not reuse or duplicate pairs beyond n.

💡 Track counts of open and close parentheses used.

Why it failed: Output includes invalid sequences with more than n pairs due to reuse. Fix by limiting open and close counts to n.

✓ Correctly limits usage to n pairs.

t3_03corner

Input{"n":4}

Expected["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in recursion depth or counts leading to missing or extra sequences.

💡 Check recursion termination condition carefully.

💡 Ensure length of string is exactly 2*n before adding to results.

💡 Verify open and close counts do not exceed n.

Why it failed: Missing or extra sequences due to off-by-one in recursion or counts. Fix by enforcing length == 2*n and open/close <= n.

✓ Correctly generates all valid sequences for n=4 with exact recursion depth.

t4_01performance

Input{"n":8}

Expectednull

⏱ Performance - must finish in 2000ms

n=8 tests performance of backtracking with pruning; brute force O(2^(2n)*n) will time out.

💡 Use pruning to avoid generating invalid sequences.

💡 Backtracking complexity is approximately O(4^n / sqrt(n)).

💡 Avoid generating all sequences and then filtering.

Why it failed: TLE due to brute force generation of all sequences. Fix by pruning invalid sequences during generation.

✓ Efficient backtracking with pruning completes within time limit.

Practice

1. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count? Board: [['5', '3', '.', '.', '7', '.', '.', '.', '.'], ['6', '.', '.', '1', '9', '5', '.', '.', '.'], ['.', '9', '8', '.', '.', '.', '.', '6', '.'], ['8', '.', '.', '.', '6', '.', '.', '.', '3'], ['4', '.', '.', '8', '.', '3', '.', '.', '1'], ['7', '.', '.', '.', '2', '.', '.', '.', '6'], ['.', '6', '.', '.', '.', '.', '2', '8', '.'], ['.', '.', '.', '4', '1', '9', '.', '.', '5'], ['.', '.', '.', '.', '8', '.', '.', '7', '9']] Code snippet:

def get_candidates(r, c):
    b = (r//3)*3 + c//3
    return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))

What is the value of candidates_len?

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify first empty cell after sorting

   Check empties and compute candidates for each; the cell with fewest candidates is chosen first.

2. Step 2: Calculate candidates for first empty cell (0,2)

   Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting candidates for (0,2) yields 3 [OK]

Hint: Count candidates by excluding row, column, box digits [OK]

Common Mistakes:

• Forgetting box constraints
• Miscounting candidates for first empty cell

2. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

3. What is the time complexity of the bitmask backtracking solution for counting all N-Queens solutions on an nxn board?

medium

A. O(n^n) because each row tries all columns independently

B. O(2^n) due to bitmask operations over all subsets of columns

C. O(n^3) from checking conflicts and iterating over rows and columns

D. O(n!) because each queen placement reduces available columns by one

Solution

1. Step 1: Identify branching factor per row

   Each row places one queen in a column not attacked by previous queens, reducing choices roughly by one each time.

2. Step 2: Calculate total recursive calls

   Thus, total calls approximate n x (n-1) x (n-2) x ... = n! permutations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid columns, yielding O(n!) complexity [OK]

Hint: N-Queens backtracking explores permutations -> O(n!) [OK]

Common Mistakes:

• Confusing bitmask ops with exponential subsets
• Assuming polynomial due to pruning

4. What is the worst-case time complexity of the optimized Sudoku solver that uses backtracking with constraint propagation and heuristic ordering of empty cells, assuming there are m empty cells?

medium

A. Polynomial time O(m^3) because constraints reduce branching drastically

B. O(9^m) because each empty cell can have up to 9 choices

C. Better than O(9^m) due to pruning, but still exponential in m

D. Linear time O(m) since heuristic ordering picks the best cell each time

Solution

1. Step 1: Understand naive complexity

   Brute force backtracking tries up to 9 choices per empty cell, so O(9^m).

2. Step 2: Effect of constraint propagation and heuristics

   Pruning reduces branching factor significantly, but worst case remains exponential in m.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heuristics improve average case but worst-case exponential remains [OK]

Hint: Heuristics prune but don't change worst-case exponential nature [OK]

Common Mistakes:

• Assuming polynomial or linear time due to heuristics
• Confusing average and worst-case complexities

5. What is the time complexity of the optimal backtracking solution for the Word Search problem, where N is the number of cells in the board and L is the length of the word?

medium

A. O(N * 4^L) because each cell explores 4 directions for each character

B. O(N * 3^L) because after the first character, each step explores up to 3 directions

C. O(N * L) because each cell is visited once per character

D. O(N^2) because the board is searched multiple times for each character

Solution

1. Step 1: Identify branching factor per recursion

   From each cell, first character has 4 directions, subsequent steps have at most 3 (excluding the cell we came from).

2. Step 2: Calculate total complexity

   For each of N cells, explore up to 3^L paths, so total time is O(N * 3^L).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3^L accounts for pruning revisits, not 4^L [OK]

Hint: Remember first step has 4 directions, next steps 3 due to no revisiting [OK]

Common Mistakes:

• Assuming 4^L for all steps
• Confusing L with N in complexity