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. Consider the following Python code implementing the bitmask backtracking solution for N-Queens II. What is the final return value of totalNQueens(4)?

easy

A. 2

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace initial call for n=4

   Start with row=0, no columns or diagonals occupied, all 4 columns available.

2. Step 2: Count valid placements recursively

   Backtracking explores all valid queen placements; for n=4, there are exactly 2 distinct solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known result for 4-queens is 2 solutions [OK]

Hint: 4-queens has 2 solutions; bitmask backtracking counts all [OK]

Common Mistakes:

• Off-by-one counting
• Confusing number of solutions with board size

2. What is the time complexity of the optimal palindrome partitioning algorithm that uses backtracking with dynamic palindrome checks by expanding around centers for palindrome verification on a string of length n?

medium

A. O(n^2) because palindrome checks are done in constant time using DP

B. O(n^3) due to checking all substrings and palindrome verification

C. O(2^n) since all partitions are generated without extra palindrome checks

D. O(n * 2^n) because each character can start a partition and palindrome checks are O(n)

Solution

1. Step 1: Identify number of partitions

   There are up to 2^(n-1) ways to partition a string of length n.

2. Step 2: Analyze palindrome check cost

   Using expand around center, palindrome check per substring is O(n) worst case, done during backtracking.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining partitions and palindrome checks yields O(n * 2^n) [OK]

Hint: Partitions grow exponentially; palindrome checks add linear factor [OK]

Common Mistakes:

• Assuming palindrome checks are O(1) without DP
• Confusing total partitions with time complexity
• Ignoring recursion stack space

3. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking

4. Suppose you want to find the lexicographically next permutation of an array where elements can be repeated and reused multiple times (infinite supply). Which modification to the standard next permutation algorithm is necessary?

hard

A. No modification needed; the standard next permutation algorithm works as is.

B. Modify the algorithm to generate all permutations with repetition and pick the next one, since in-place approach fails.

C. Adjust the pivot search to consider repeated elements and skip duplicates to avoid redundant swaps.

D. Use a backtracking approach that allows repeated elements and generates permutations with repetition.

Solution

1. Step 1: Understand the problem variant

   Allowing repeated use of elements means permutations with repetition, which standard next permutation does not handle as it assumes fixed elements.

2. Step 2: Identify correct approach

   Backtracking that generates permutations with repetition is required, as in-place next permutation only rearranges existing elements without reuse.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Standard next permutation assumes fixed elements; repeated reuse requires backtracking [OK]

Hint: Next permutation assumes fixed elements; reuse needs backtracking [OK]

Common Mistakes:

• Thinking standard algorithm handles reuse
• Trying to modify pivot logic only

5. Suppose the Sudoku solver is modified so that digits can be reused multiple times in the same row, column, or box (i.e., constraints are relaxed). Which of the following statements about the backtracking algorithm is true?

hard

A. Constraint checks can be removed, and backtracking reduces to brute force filling

B. Heuristic ordering of empty cells becomes unnecessary since constraints are relaxed

C. The existing backtracking with constraint propagation still works correctly without changes

D. The problem becomes trivial and can be solved in linear time by filling all empty cells with '1'

Solution

1. Step 1: Understand effect of relaxing constraints

   Allowing repeated digits removes Sudoku constraints, so no need to check row, column, or box validity.

2. Step 2: Impact on backtracking algorithm

   Backtracking degenerates to brute force filling since any digit can be placed anywhere; constraint propagation is useless.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Relaxed constraints mean no pruning, so backtracking is brute force [OK]

Hint: Relaxed constraints remove pruning, reverting to brute force [OK]

Common Mistakes:

• Assuming heuristics still help
• Thinking problem becomes trivial linear time