Palindrome Partitioning

▶

Steps

setup

Start Backtracking at index 0 with empty path

The algorithm begins by calling backtrack with start index 0 and an empty path to build palindrome partitions from the start of the string.

💡 This initializes the recursion and sets up the empty path that will be built up with palindrome substrings.

Line:

backtrack(0, [])

💡 The recursion tree root represents the initial state before any substrings are chosen.

compare

Check substring s[0:1] = 'a' for palindrome

The algorithm checks if the substring from index 0 to 0 ('a') is a palindrome by expanding around its boundaries.

💡 Checking palindrome validity is crucial to decide if this substring can be part of the partition path.

Line:

if is_palindrome(start, end):

💡 Single characters are always palindromes, so this substring is valid.

traverse

Add substring 'a' to path and recurse from index 1

Since 'a' is palindrome, it is appended to the path and backtrack is called recursively starting at index 1 to find further partitions.

💡 Adding a valid palindrome substring extends the current partition path and explores deeper partitions.

Line:

path.append(s[start:end+1])
backtrack(end+1, path)

💡 The recursion explores partitions starting after the chosen substring.

compare

Check substring s[1:2] = 'a' for palindrome

At index 1, the substring 'a' is checked for palindrome validity.

💡 Again, single characters are palindromes, so this substring is valid for partitioning.

Line:

if is_palindrome(start, end):

💡 The algorithm confirms this substring can extend the current path.

traverse

Add substring 'a' to path and recurse from index 2

The substring 'a' is appended to the path, and backtrack is called recursively starting at index 2.

💡 This step extends the current partition path and explores further partitions starting at the next index.

Line:

path.append(s[start:end+1])
backtrack(end+1, path)

💡 The recursion continues deeper with path ['a', 'a'].

compare

Check substring s[2:3] = 'b' for palindrome

At index 2, the substring 'b' is checked for palindrome validity.

💡 Single characters are palindromes, so this substring is valid for partitioning.

Line:

if is_palindrome(start, end):

💡 The algorithm confirms this substring can complete a partition path.

traverse

Add substring 'b' to path and recurse from index 3 (end)

The substring 'b' is appended to the path, and backtrack is called recursively starting at index 3, which is the end of the string.

💡 Reaching the end means a complete palindrome partition is found.

Line:

path.append(s[start:end+1])
backtrack(end+1, path)

💡 The recursion reaches a leaf node representing a complete valid partition.

reconstruct

Add current path ['a', 'a', 'b'] to results

Since start index equals string length, the current path is a complete palindrome partition and is added to the results list.

💡 This step collects a valid answer found by the recursion.

Line:

if start == len(s):
    result.append(path[:])
    return

💡 Leaves in the recursion tree correspond to complete valid partitions.

delete

Backtrack: remove 'b' and try next substring at index 2

The algorithm backtracks by removing 'b' from the path and tries other substrings starting at index 2 (none remain).

💡 Backtracking removes the last choice to explore alternative partitions.

Line:

path.pop()

💡 Backtracking enables exploring all possible partitions by undoing previous choices.

delete

Backtrack: remove 'a' and try substring s[1:3] = 'ab'

Backtracking removes the last 'a' from the path and tries the next substring 'ab' starting at index 1, which is checked for palindrome.

💡 Trying longer substrings explores different partition possibilities.

Line:

path.pop()
if is_palindrome(start, end):

💡 Non-palindromic substrings are pruned and not explored further.

delete

Backtrack: remove 'a' and try substring s[0:2] = 'aa'

Backtracking removes the first 'a' from the path and tries the substring 'aa' starting at index 0, checking if it is palindrome.

💡 Trying longer substrings at the root explores alternative partitions.

Line:

path.pop()
if is_palindrome(start, end):

💡 Longer palindromic substrings can form different partitions.

traverse

Add substring 'aa' to path and recurse from index 2

The substring 'aa' is appended to the path, and backtrack is called recursively starting at index 2.

💡 This explores partitions starting after the substring 'aa'.

Line:

path.append(s[start:end+1])
backtrack(end+1, path)

💡 The recursion explores partitions with path ['aa'].

compare

Check substring s[2:3] = 'b' for palindrome

At index 2, the substring 'b' is checked for palindrome validity.

💡 Single characters are palindromes and can complete the partition.

Line:

if is_palindrome(start, end):

💡 The substring 'b' can complete the partition path.

traverse

Add substring 'b' to path and recurse from index 3 (end)

The substring 'b' is appended to the path, and backtrack is called recursively starting at index 3, the end of the string.

💡 Reaching the end means a complete palindrome partition is found.

Line:

path.append(s[start:end+1])
backtrack(end+1, path)

💡 The recursion reaches a leaf node representing a complete valid partition.

reconstruct

Add current path ['aa', 'b'] to results

Since start index equals string length, the current path is a complete palindrome partition and is added to the results list.

💡 This step collects another valid answer found by the recursion.

Line:

if start == len(s):
    result.append(path[:])
    return

💡 Leaves in the recursion tree correspond to complete valid partitions.

backtracking

Backtrack to root and complete exploration

The algorithm backtracks fully to the root call, having explored all palindrome partitions starting at index 0.

💡 Backtracking completes the exploration of all possible partitions.

Line:

path.pop()

💡 All valid partitions have been collected in the results list.

def partition(s):
    def is_palindrome(left, right):
        while left < right:  # STEP 2,4,6,13 palindrome checks
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):  # STEP 8,15 collect answer
            result.append(path[:])
            return
        for end in range(start, len(s)):  # STEP 1,2,4,6,13 loop over substrings
            if is_palindrome(start, end):  # STEP 2,4,6,13 palindrome check
                path.append(s[start:end+1])  # STEP 3,5,7,12,14 add substring
                backtrack(end+1, path)  # STEP 3,5,7,12,14 recurse
                path.pop()  # STEP 9,10,11,16 backtrack

    result = []
    backtrack(0, [])  # STEP 1 start recursion
    return result

📊

Palindrome Partitioning - Watch the Algorithm Execute, Step by Step

Watching each recursive call and decision reveals how the algorithm systematically explores all partitions and prunes invalid paths, making the backtracking process clear and intuitive.

enteringstart=0path=[]

Call Path (current → root)

backtrack(0, [])

Remaining

end=0end=1end=2

choosingstart=0path=[]

Call Path (current → root)

backtrack(0, [])

Remaining

end=1end=2

enteringstart=1path=["a"]

Call Path (current → root)

backtrack(1, ['a'])

backtrack(0, [])

Remaining

end=1end=2

Partial: [a]

choosingstart=1path=["a"]

Call Path (current → root)

backtrack(1, ['a'])

backtrack(0, [])

Remaining

end=2

Partial: [a]

enteringstart=2path=["a","a"]

Call Path (current → root)

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

backtrack(1, ['a'])

backtrack(0, [])

Remaining

end=2

Partial: [a, a]

choosingstart=2path=["a","a"]

Call Path (current → root)

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

backtrack(1, ['a'])

backtrack(0, [])

Partial: [a, a]

enteringstart=3path=["a","a","b"]

Call Path (current → root)

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

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

backtrack(1, ['a'])

backtrack(0, [])

Partial: [a, a, b]

backtrackingstart=3path=["a","a","b"]

Call Path (current → root)

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

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

backtrack(1, ['a'])

backtrack(0, [])

Partial: [a, a, b]

Found 1: [a,a,b]

choosingstart=2path=["a","a"]

Call Path (current → root)

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

backtrack(1, ['a'])

backtrack(0, [])

Tried

end=2

Partial: [a, a]

Found 1: [a,a,b]

choosingstart=1path=["a"]

Call Path (current → root)

backtrack(1, ['a'])

backtrack(0, [])

Tried

end=1end=2

Partial: [a]

✂ substring 'ab' is not palindrome

Found 1: [a,a,b]

choosingstart=0path=[]

Call Path (current → root)

backtrack(0, [])

Tried

end=0

Remaining

end=2

Found 1: [a,a,b]

enteringstart=2path=["aa"]

Call Path (current → root)

backtrack(2, ['aa'])

backtrack(0, [])

Remaining

end=2

Partial: [aa]

Found 1: [a,a,b]

choosingstart=2path=["aa"]

Call Path (current → root)

backtrack(2, ['aa'])

backtrack(0, [])

Partial: [aa]

Found 1: [a,a,b]

enteringstart=3path=["aa","b"]

Call Path (current → root)

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

backtrack(2, ['aa'])

backtrack(0, [])

Partial: [aa, b]

Found 1: [a,a,b]

backtrackingstart=3path=["aa","b"]

Call Path (current → root)

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

backtrack(2, ['aa'])

backtrack(0, [])

Partial: [aa, b]

Found 2: [a,a,b] [aa,b]

backtrackingstart=0path=[]

Call Path (current → root)

backtrack(0, [])

Tried

end=0end=2

Found 2: [a,a,b] [aa,b]

Key Takeaways

✓ Backtracking systematically explores all substring partitions by recursively choosing palindromic substrings and backtracking to try alternatives.

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

✓ Palindrome checks prune invalid branches early, preventing unnecessary recursion and improving efficiency.

Seeing the pruning visually clarifies why the algorithm avoids exploring non-palindromic substrings.

✓ The recursion tree structure corresponds directly to partial palindrome partitions, with leaves representing complete valid partitions.

This concrete mapping helps understand how partial solutions build up and how answers are collected.

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. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

3. Identify the bug in the following code snippet for getPermutation:

medium

A. Line 6: k is not converted to zero-based index before calculations.

B. Line 2: factorial array initialization is incorrect.

C. Line 10: The index calculation uses integer division incorrectly.

D. Line 12: numbers.pop(idx) should be numbers.remove(idx).

Solution

1. Step 1: Check k adjustment

   k must be decremented by 1 to convert to zero-based indexing before using factorial divisions.

2. Step 2: Understand impact of missing k -= 1

   Without this, idx calculation is off by one, leading to incorrect permutation output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing k -= 1 causes wrong indexing and wrong permutation [OK]

Hint: Always convert k to zero-based before factorial indexing [OK]

Common Mistakes:

• Forgetting zero-based index adjustment
• Misusing pop vs remove
• Incorrect factorial initialization

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

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