Palindrome Partitioning Using Backtracking in DSA Python

Mental Model

We try to split a string into parts where each part reads the same forwards and backwards. We explore all ways to do this by trying each possible cut and going back if it doesn't work.

Analogy: Imagine cutting a long ribbon into smaller pieces where each piece is a perfect mirror image if folded. You try cutting at different points, and if a piece isn't symmetrical, you undo the cut and try another place.

s = "a b a c"
Partitions: []
Try cuts: a | b a c
            ↑
Check if 'a' is palindrome -> yes
Add 'a' to partitions
Partitions: [a]
Try cuts on remaining: b | a c
                      ↑

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" so every part is a palindrome

Step 1: Check substring 'a' (index 0 to 0), it is palindrome, add to current partition

Partitions: [a]
Remaining string: 'ab'

Why: Start with smallest possible palindrome to build partitions

Step 2: Check substring 'a' (index 1 to 1), it is palindrome, add to current partition

Partitions: [a, a]
Remaining string: 'b'

Why: Continue partitioning remaining string with palindrome parts

Step 3: Check substring 'b' (index 2 to 2), it is palindrome, add to current partition

Partitions: [a, a, b]
Remaining string: '' (empty)

Why: Reached end of string with all palindrome parts, save this partition

Step 4: Backtrack: remove last part 'b', try next substring 'ab' (index 1 to 2), not palindrome, discard

Partitions: [a, a]
Remaining string: 'b'

Why: Try other partitions by undoing last choice when no palindrome found

Step 5: Backtrack: remove last part 'a', try substring 'aa' (index 0 to 1), palindrome, add to partition

Partitions: [aa]
Remaining string: 'b'

Why: Try longer palindrome parts starting from beginning

Step 6: Check substring 'b' (index 2 to 2), palindrome, add to partition

Partitions: [aa, b]
Remaining string: '' (empty)

Why: Reached end with another valid partition, save it

Result:

Partitions found:
[a, a, b]
[aa, b]

Annotated Code

DSA Python

from typing import List

class PalindromePartitioning:
    def __init__(self):
        self.result = []

    def is_palindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(self, s: str, start: int, path: List[str]) -> None:
        if start == len(s):
            self.result.append(path.copy())
            return
        for end in range(start, len(s)):
            if self.is_palindrome(s, start, end):
                path.append(s[start:end+1])
                self.backtrack(s, end + 1, path)
                path.pop()

    def partition(self, s: str) -> List[List[str]]:
        self.result.clear()
        self.backtrack(s, 0, [])
        return self.result

if __name__ == '__main__':
    s = "aab"
    solver = PalindromePartitioning()
    partitions = solver.partition(s)
    for p in partitions:
        print(p)

while left < right: if s[left] != s[right]: return False left += 1 right -= 1

Check if substring s[left:right] is palindrome by comparing characters from ends inward

if start == len(s): self.result.append(path.copy()) return

If reached end of string, save current partition path as a valid solution

for end in range(start, len(s)): if self.is_palindrome(s, start, end): path.append(s[start:end+1]) self.backtrack(s, end + 1, path) path.pop()

Try all possible substrings from start; if palindrome, add to path and recurse; then backtrack

Output

['a', 'a', 'b']

['aa', 'b']

Complexity Analysis

Time: O(N * 2^N) because each character can be either a cut or not, and palindrome checks take O(N)

Space: O(N) for recursion stack and path storage, plus O(N) for palindrome checks

vs Alternative: Naive approach without backtracking tries all partitions blindly; backtracking prunes invalid paths early, saving time

Edge Cases

Empty string

Returns [[]]

DSA Python

if start == len(s):

String with all identical characters, e.g., "aaa"

Finds all partitions where each substring is palindrome, including single chars and longer substrings

DSA Python

if self.is_palindrome(s, start, end):

String with no palindrome longer than 1, e.g., "abc"

Partitions only single characters as palindromes

DSA Python

if self.is_palindrome(s, start, end):

When to Use This Pattern

When asked to find all ways to split a string into palindrome parts, use backtracking to explore all partitions and prune invalid ones.

Common Mistakes

Mistake: Not backtracking (removing last added substring) after recursive call, causing incorrect partitions
Fix: Add path.pop() after recursive call to undo last choice

Mistake: Checking palindrome incorrectly or inefficiently causing wrong results or slow code
Fix: Use two-pointer check from ends inward for palindrome verification

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need to find all palindrome partitions of a string.

Try every cut, check palindrome, recurse, and undo choices to explore all valid partitions.

Practice

1. What is the main goal of palindrome partitioning using backtracking on a string s?

easy

A. To split s into all possible substrings where each substring is a palindrome

B. To find the longest palindrome substring in s

C. To count the total number of palindromes in s

D. To reverse the string s and check if it is a palindrome

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing the string into parts where each part reads the same forwards and backwards.

2. Step 2: Role of backtracking

   Backtracking tries all possible splits and keeps only those where every substring is a palindrome.

3. Final Answer:

   To split s into all possible substrings where each substring is a palindrome -> Option A

4. Quick Check:

   Palindrome partitioning = all palindrome substrings [OK]

Hint: Backtracking tries all splits keeping palindrome parts [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it counts palindromes instead of listing partitions
• Assuming it just reverses the string

2. Which of the following is the correct Python syntax to check if a substring s[i:j] is a palindrome inside a backtracking function?

easy

A. if s[i:j] == s[j:i]:

B. if s[i:j] == reversed(s[i:j]):

C. if s[i:j] == s[i:j][::-1]:

D. if s[i:j] == s[j:i][::-1]:

Solution

1. Step 1: Understand Python slicing and reversal

   Using s[i:j][::-1] reverses the substring from index i to j-1.

2. Step 2: Compare substring with its reverse

   If s[i:j] equals its reversed version, it is a palindrome.

3. Final Answer:

   if s[i:j] == s[i:j][::-1]: -> Option C

4. Quick Check:

   Substring == reversed substring [OK]

Hint: Use slicing with [::-1] to reverse substring [OK]

Common Mistakes:

• Using reversed() which returns an iterator, not a string
• Comparing s[i:j] with s[j:i] which is empty or invalid
• Incorrect slicing order causing empty strings

3. What will be the output of the following code snippet?

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path[:])
        return
    for end in range(start + 1, len(s) + 1):
        if s[start:end] == s[start:end][::-1]:
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aab', 0, [], result)
print(result)

medium

A. [['a', 'a', 'b'], ['aa', 'b']]

B. [['a', 'ab'], ['aa', 'b']]

C. [['a', 'a', 'b']]

D. [['aa', 'ab']]

Solution

1. Step 1: Trace backtracking on 'aab'

   Partitions found are ['a','a','b'] and ['aa','b'] because 'a', 'aa', and 'b' are palindromes.

2. Step 2: Confirm all palindrome partitions collected

   Both partitions are added to result list before printing.

3. Final Answer:

   [['a', 'a', 'b'], ['aa', 'b']] -> Option A

4. Quick Check:

   All palindrome partitions = [['a', 'a', 'b'], ['aa', 'b']] [OK]

Hint: Check all palindrome splits recursively [OK]

Common Mistakes:

• Missing the partition ['aa', 'b']
• Including non-palindrome substrings like 'ab'
• Not popping path after recursion causing wrong results

4. Identify the error in the following backtracking code for palindrome partitioning:

def backtrack(s, start, path, result):
    if start == len(s):
        result.append(path)
        return
    for end in range(start + 1, len(s) + 1):
        if s[start:end] == s[start:end][::-1]:
            path.append(s[start:end])
            backtrack(s, end, path, result)
            path.pop()

result = []
backtrack('aba', 0, [], result)
print(result)

medium

A. The loop range should start from start, not start + 1

B. The palindrome check is incorrect

C. Missing return statement after appending to result

D. Appending path directly causes all results to be the same list

Solution

1. Step 1: Understand list reference behavior in Python

   Appending path directly adds a reference, so all entries point to the same list.

2. Step 2: Fix by appending a copy of path

   Use result.append(path[:]) to save a snapshot of current path.

3. Final Answer:

   Appending path directly causes all results to be the same list -> Option D

4. Quick Check:

   Append copy of path, not path itself [OK]

Hint: Always append a copy of path to result [OK]

Common Mistakes:

• Appending the same list reference causing duplicate results
• Incorrect palindrome check logic
• Wrong loop range causing missed substrings

5. Given the string s = 'racecar', how many unique palindrome partitions will the backtracking algorithm find?

hard

A. 4

B. 8

C. 6

D. 10

Solution

1. Step 1: List all palindrome partitions of 'racecar'

   Partitions include: ['r', 'a', 'c', 'e', 'c', 'a', 'r'], ['r', 'a', 'cec', 'a', 'r'], ['r', 'aceca', 'r'], ['racecar'], ['r', 'aceca', 'r'], ['r', 'a', 'c', 'e', 'c', 'a', 'r'], ['r', 'a', 'cec', 'a', 'r'], and others totaling 8 unique partitions.

2. Step 2: Confirm count by backtracking logic

   Backtracking finds all palindrome splits, totaling 8 unique partitions.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Unique palindrome partitions count = 8 [OK]

Hint: Count all palindrome splits carefully [OK]

Common Mistakes:

• Counting non-palindrome substrings as partitions
• Missing longer palindrome substrings like 'aceca'
• Assuming only single-character partitions