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 Python code snippet implementing the optimal backtracking approach for Expression Add Operators. Given input num = "123" and target = 6, what is the content of the result list after the function completes?

from typing import List

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)):
            if i != index and num[index] == '0':
                break
            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

easy

A. ["1+23", "12+3"]

B. ["123"]

C. ["1+2+3", "123"]

D. ["1+2+3"]

Solution

1. Step 1: Trace backtracking calls for num="123", target=6

   At index=0, path starts with "1". Then at index=1, add '+' and "2", evaluated=3. Then at index=2, add '+' and "3", evaluated=6, matches target, so "1+2+3" is added.

2. Step 2: Check other possible expressions

   "123" alone evaluates to 123, not 6. "1+23"=24, "12+3"=15, none equal 6. So only "1+2+3" is in result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only "1+2+3" sums to 6 [OK]

Hint: Only "1+2+3" equals 6 with given operators [OK]

Common Mistakes:

• Assuming "123" or "1+23" equals target

2. Given the following code for palindrome partitioning, what is the final output when input string s = "aab" is passed to partition(s)?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

easy

A. [["a", "a", "b"]]

B. [["a", "ab"], ["aa", "b"]]

C. [["a", "a", "b"], ["aa", "b"]]

D. [["aab"]]

Solution

1. Step 1: Trace backtrack calls for s="aab"

   Start=0, path=[]; check substrings: "a" (palindrome), "aa" (palindrome), "aab" (not palindrome). Explore "a" -> backtrack(1, ["a"]), then "a" -> backtrack(2, ["a", "a"]), then "b" -> backtrack(3, ["a", "a", "b"]) adds ["a", "a", "b"] to result.

2. Step 2: Explore "aa" substring

   From start=0, choose "aa" -> backtrack(2, ["aa"]), then "b" -> backtrack(3, ["aa", "b"]) adds ["aa", "b"] to result.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both partitions contain only palindromes and cover entire string [OK]

Hint: Trace recursion and palindrome checks carefully [OK]

Common Mistakes:

• Including non-palindromic substrings like "ab"
• Missing one valid partition
• Returning partial partitions

3. The following code attempts to solve N-Queens using bitmask backtracking. Which line contains a subtle bug that can cause invalid solutions or missed solutions?

medium

A. Line extracting rightmost 1-bit as position

B. Line updating diag1 and diag2 with incorrect bit shifts in recursive call

C. Line computing available_positions with bitmask and negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify bit shift directions for diagonals

   diag1 (major diagonal) must be shifted left by 1, diag2 (minor diagonal) shifted right by 1 to reflect next row attacks.

2. Step 2: Check recursive call shifts

   The code incorrectly shifts diag1 right and diag2 left, reversing the attack directions, causing invalid pruning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct diagonal shifts are diag1 << 1 and diag2 >> 1 [OK]

Hint: Diagonal attack masks must shift opposite directions each row [OK]

Common Mistakes:

• Swapping diag1 and diag2 shifts
• Not resetting board after recursion
• Incorrect bitmask negation

4. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path)  # Line X
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

medium

A. Line 6: palindrome check misses single character substrings

B. Line X: appending path without copying causes shared references

C. Line 12: for loop range should be from start+1 to len(s)+1

D. Line 15: missing path.pop() after backtrack call

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so later modifications affect all stored results.

2. Step 2: Correct approach

   Use result.append(path[:]) to append a copy, preserving each partition snapshot.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Shared references cause incorrect final partitions [OK]

Hint: Always append a copy of path to results [OK]

Common Mistakes:

• Forgetting to copy path before appending
• Incorrect palindrome check boundaries
• Forgetting to pop after recursion

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.