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

2. Given the following code for generating unique permutations, what is the final output when the input is [1,1,2]?

from typing import List

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

print(permuteUnique([1,1,2]))

easy

A. [[1,2,1],[1,1,2],[2,1,1]]

B. [[1,1,2],[2,1,1],[1,2,1]]

C. [[1,1,2],[1,2,1],[2,1,1]]

D. [[2,1,1],[1,1,2],[1,2,1]]

Solution

1. Step 1: Trace initial sorting and first level of recursion

   Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.

2. Step 2: Trace subsequent recursion and skipping duplicates

   At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected unique permutations in lex order [OK]

Hint: Sort input and skip duplicates with seen set [OK]

Common Mistakes:

• Misordering output permutations due to swap order

3. Given the following iterative backtracking code snippet for restoring IP addresses, what is the final output when the input string is "25525511135"?

from typing import List

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]  # (start index, path)
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
                continue
            stack.append((start + length, path + [segment]))
    return res

print(restore_ip_addresses("25525511135"))

easy

A. ["255.255.11.135"]

B. ["255.255.111.35", "255.255.11.135"]

C. ["255.255.11.135", "255.255.111.35"]

D. ["255.255.111.35"]

Solution

1. Step 1: Trace initial stack and first expansions

   Start with (0, []). Segments like '255', '25', '2' are pushed. Valid segments are checked for leading zeros and range.

2. Step 2: Identify valid IP addresses found

   Two valid IPs are found: "255.255.11.135" and "255.255.111.35". Both use all characters and have 4 segments.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both valid IPs appear in the result list [OK]

Hint: Valid IPs must have 4 segments and consume entire string [OK]

Common Mistakes:

• Confusing order of results
• Missing one valid IP due to pruning

4. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting

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