Generate Parentheses

▶

Steps

setup

Initialize recursion with empty string and zero counts

The algorithm starts by calling backtrack with an empty list s, and both open_count and close_count set to 0.

💡 This sets the base state from which all valid parentheses sequences will be built.

Line:

backtrack([], 0, 0)

💡 The recursion tree root represents the empty sequence with no parentheses added yet.

expand

Add '(' since open_count < n

Since open_count (0) is less than n (3), '(' is appended to s and backtrack is called recursively with open_count incremented.

💡 Adding '(' is always valid if we haven't used all open parentheses yet.

Line:

s.append('(')
backtrack(s, open_count + 1, close_count)
s.pop()

💡 The algorithm explores the branch where the next character is '(' to build valid sequences.

expand

Add '(' again since open_count < n

Again, open_count (1) is less than n (3), so '(' is appended and recursion continues with open_count incremented.

💡 The algorithm continues to add '(' to build the left side of the parentheses sequence.

Line:

s.append('(')
backtrack(s, open_count + 1, close_count)
s.pop()

💡 This deepens the recursion tree, building sequences with multiple '(' before adding ')'.

expand

Add '(' once more since open_count < n

Open_count (2) is still less than n (3), so '(' is appended and recursion proceeds with open_count incremented.

💡 This completes the maximum number of '(' that can be added for n=3.

Line:

s.append('(')
backtrack(s, open_count + 1, close_count)
s.pop()

💡 The recursion has reached the deepest left branch with all '(' added.

expand

Add ')' since close_count < open_count

Cannot add '(' anymore because open_count == n, so ')' is appended and recursion continues with close_count incremented.

💡 The algorithm now starts closing parentheses to form valid sequences.

Line:

s.append(')')
backtrack(s, open_count, close_count + 1)
s.pop()

💡 The algorithm backtracks by adding ')' to balance the previously added '('.

expand

Add ')' again since close_count < open_count

Still cannot add '(' (open_count == n), so ')' is appended again and recursion continues with close_count incremented.

💡 The algorithm continues closing parentheses to approach a complete valid sequence.

Line:

s.append(')')
backtrack(s, open_count, close_count + 1)
s.pop()

💡 The recursion deepens by adding more ')' to balance the sequence.

expand

Add ')' to complete a valid sequence

Appending ')' again since close_count (2) < open_count (3) completes the sequence length 2*n (6).

💡 A complete valid parentheses sequence is formed and added to the results.

Line:

if len(s) == 2 * n:
    result.append(''.join(s))
    return

💡 The leaf node corresponds to a valid sequence '((()))' collected as an answer.

backtracking

Backtrack and try adding ')' earlier in the sequence

After collecting '((()))', the algorithm backtracks by removing the last ')' and tries adding ')' at an earlier position.

💡 Backtracking allows exploring alternative valid sequences by undoing previous choices.

Line:

s.pop()  # backtrack
if close_count < open_count:
    s.append(')')

💡 Backtracking explores all branches by undoing and trying other options.

expand

Add ')' at second to last position and continue recursion

The algorithm adds ')' at this earlier position and recurses to build sequences like '(()())'.

💡 Trying ')' earlier creates new valid sequences different from the first one found.

Line:

s.append(')')
backtrack(s, open_count, close_count + 1)
s.pop()

💡 This branch explores sequences with mixed '(' and ')' placements.

expand

Add '(' after adding ')' to explore new branch

Since open_count (2) < n (3), the algorithm adds '(' to explore sequences like '(()()'.

💡 Adding '(' after ')' allows building sequences with interleaved parentheses.

Line:

s.append('(')
backtrack(s, open_count + 1, close_count)
s.pop()

💡 This step shows the algorithm exploring different branches by mixing '(' and ')'.

def generateParenthesis(n):
    result = []
    def backtrack(s, open_count, close_count):  # STEP 1
        if len(s) == 2 * n:  # STEP 7, 12, 20, 21
            result.append(''.join(s))
            return
        if open_count < n:  # STEP 2,3,4,9,10,14,16
            s.append('(')
            backtrack(s, open_count + 1, close_count)
            s.pop()
        if close_count < open_count:  # STEP 5,6,11,15,19,21
            s.append(')')
            backtrack(s, open_count, close_count + 1)
            s.pop()
    backtrack([], 0, 0)  # STEP 1
    return result

if __name__ == '__main__':
    print(generateParenthesis(3))

📊

Generate Parentheses - Watch the Algorithm Execute, Step by Step

Watching each recursive call and backtrack reveals how the algorithm prunes invalid sequences early and efficiently builds all valid combinations.

enterings=[]open_count=0close_count=0

Call Path (current → root)

backtrack([],0,0)

Remaining

add '(' if open_count < nadd ')' if close_count < open_count

enterings=["("]open_count=1close_count=0

Call Path (current → root)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add '(' if open_count < nadd ')' if close_count < open_count

Partial: [(]

enterings=["(","("]open_count=2close_count=0

Call Path (current → root)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add '(' if open_count < nadd ')' if close_count < open_count

Partial: [(, (]

enterings=["(","(","("]open_count=3close_count=0

Call Path (current → root)

backtrack(['(', '(', '('],3,0)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add '(' if open_count < nadd ')' if close_count < open_count

Partial: [(, (, (]

enterings=["(","(","(",")"]open_count=3close_count=1

Call Path (current → root)

backtrack(['(', '(', '(', ')'],3,1)

backtrack(['(', '(', '('],3,0)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add ')' if close_count < open_count

Partial: [(, (, (, )]

enterings=["(","(","(",")",")"]open_count=3close_count=2

Call Path (current → root)

backtrack(['(', '(', '(', ')', ')'],3,2)

backtrack(['(', '(', '(', ')'],3,1)

backtrack(['(', '(', '('],3,0)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add ')' if close_count < open_count

Partial: [(, (, (, ), )]

backtrackings=["(","(","(",")",")",")"]open_count=3close_count=3

Call Path (current → root)

backtrack(['(', '(', '(', ')', ')', ')'],3,3)

backtrack(['(', '(', '(', ')', ')'],3,2)

backtrack(['(', '(', '(', ')'],3,1)

backtrack(['(', '(', '('],3,0)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Partial: [(, (, (, ), ), )]

Found 1: [((()))]

choosings=["(","(","("]open_count=3close_count=2

Call Path (current → root)

backtrack(['(', '(', '('],3,0)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Tried

add ')'

Remaining

add '(' if open_count < n

Partial: [(, (, (]

Found 1: [((()))]

enterings=["(","(",")"]open_count=2close_count=1

Call Path (current → root)

backtrack(['(', '(', ')'],2,1)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add '(' if open_count < nadd ')' if close_count < open_count

Partial: [(, (, )]

Found 1: [((()))]

enterings=["(","(",")","("]open_count=3close_count=1

Call Path (current → root)

backtrack(['(', '(', ')', '('],3,1)

backtrack(['(', '(', ')'],2,1)

backtrack(['(', '('],2,0)

backtrack(['('],1,0)

backtrack([],0,0)

Remaining

add ')' if close_count < open_count

Partial: [(, (, ), (]

Found 1: [((()))]

Key Takeaways

✓ Backtracking builds sequences incrementally and backtracks to explore all valid combinations.

This insight is hard to see from code alone because the recursion and backtracking flow is implicit and complex.

✓ The algorithm prunes invalid sequences early by only adding ')' when close_count < open_count.

This pruning avoids generating invalid sequences, making the algorithm efficient.

✓ Each leaf node in the recursion tree corresponds to a complete valid parentheses sequence collected as an answer.

Seeing the leaf nodes as answers clarifies how the recursion tree maps to the final output.

Practice

1. 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

2. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

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

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 time complexity of the BFS approach for removing invalid parentheses from a string of length n, considering the worst case?

medium

A. O(n * 2^n) because there can be up to 2^n states and each validity check takes O(n)

B. O(n!) because permutations of removals are explored

C. O(2^n) because BFS explores all subsets of characters without repeated checks

D. O(n^2) because each level removes one character and checks validity in O(n)

Solution

1. Step 1: Count possible states

   Each character can be either removed or kept, so up to 2^n possible strings can be generated.

2. Step 2: Analyze per-state cost

   Each string requires an O(n) validity check, so total worst-case time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   2^n states times O(n) validity checks [OK]

Hint: 2^n states times O(n) validity checks [OK]

Common Mistakes:

• Confusing O(n^2) with BFS complexity
• Ignoring validity check cost
• Assuming factorial complexity

5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column conflicts are ignored), but diagonal conflicts still apply. Which modification to the bitmask backtracking approach correctly counts all valid solutions under this relaxed constraint?

hard

A. Track only column bitmask and ignore diagonal bitmasks

B. Keep all bitmasks but allow queens to be placed in any column regardless of conflicts

C. Remove the column bitmask and only track diagonal bitmasks for conflicts

D. Use a greedy approach placing queens in the first available diagonal position per row

Solution

Solution:

1. Step 1: Analyze relaxed constraints

   Column conflicts are ignored, so column bitmask is unnecessary; diagonal conflicts remain.

2. Step 2: Modify bitmask tracking accordingly

   Remove column bitmask from conflict checks and recursive calls; keep positive and negative diagonal bitmasks to prune invalid placements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Removing column mask matches relaxed rules and preserves diagonal conflict checks [OK]

Hint: Ignore column mask when column conflicts are allowed [OK]

Common Mistakes:

• Ignoring diagonals too
• Allowing all placements without pruning