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 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. You need to find the k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?

easy

A. Use a greedy algorithm that swaps elements to reach the k-th permutation directly.

B. Compute factorial values to determine each digit's position and build the permutation directly.

C. Use dynamic programming to count permutations and reconstruct the k-th sequence.

D. Generate all permutations using backtracking and return the k-th one.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.

2. Step 2: Identify the approach that uses factorial number system

   Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Factorial-based direct computation is optimal and avoids timeouts [OK]

Hint: Factorials let you jump directly to the k-th permutation [OK]

Common Mistakes:

• Thinking greedy swaps can find k-th permutation efficiently
• Assuming DP is needed here
• Trying to generate all permutations for large n

3. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

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

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

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

5. What is the worst-case time complexity of the optimized Sudoku solver that uses backtracking with constraint propagation and heuristic ordering of empty cells, assuming there are m empty cells?

medium

A. Polynomial time O(m^3) because constraints reduce branching drastically

B. O(9^m) because each empty cell can have up to 9 choices

C. Better than O(9^m) due to pruning, but still exponential in m

D. Linear time O(m) since heuristic ordering picks the best cell each time

Solution

1. Step 1: Understand naive complexity

   Brute force backtracking tries up to 9 choices per empty cell, so O(9^m).

2. Step 2: Effect of constraint propagation and heuristics

   Pruning reduces branching factor significantly, but worst case remains exponential in m.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heuristics improve average case but worst-case exponential remains [OK]

Hint: Heuristics prune but don't change worst-case exponential nature [OK]

Common Mistakes:

• Assuming polynomial or linear time due to heuristics
• Confusing average and worst-case complexities