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.