Palindrome Partitioning Using Backtracking in DSA Python - Execution Trace

Concept Flow - Palindrome Partitioning Using Backtracking

Start with empty path

↓

Choose substring from start

↓

Check if substring is palindrome?

No→Discard substring, try next

Yes↓

Add substring to path

↓

Recurse with remaining string

↓

If no string left

→Add path to results

↓

Backtrack: remove last substring

↩Back to choose next substring

We try all substrings from the start, keep those that are palindromes, recurse on the rest, and backtrack to explore all partitions.

Execution Sample

DSA Python

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

This code finds all palindrome partitions of string s using backtracking.

Execution Table

Step	Operation	Substring Chosen	Is Palindrome?	Path (Current Partition)	Remaining String	Action
1	Start			[]	aab	Begin with empty path
2	Choose substring	a	Yes	["a"]	ab	Add 'a' to path, recurse
3	Choose substring	a	Yes	["a", "a"]	b	Add 'a' to path, recurse
4	Choose substring	b	Yes	["a", "a", "b"]		Add 'b' to path, recurse
5	Reached end			["a", "a", "b"]		Add path to results
6	Backtrack			["a", "a"]	b	Remove 'b', try next substring
7	No more substrings		No	["a", "a"]	b	Backtrack again
8	Backtrack			["a"]	ab	Remove last 'a', try next substring
9	Choose substring	ab	No	["a"]	ab	Discard 'ab', try next
10	Backtrack			[]	aab	Remove 'a', try next substring
11	Choose substring	aa	Yes	["aa"]	b	Add 'aa' to path, recurse
12	Choose substring	b	Yes	["aa", "b"]		Add 'b' to path, recurse
13	Reached end			["aa", "b"]		Add path to results
14	Backtrack			["aa"]	b	Remove 'b', try next substring
15	No more substrings		No	["aa"]	b	Backtrack again
16	Backtrack			[]	aab	Remove 'aa', try next substring
17	Choose substring	aab	No	[]	aab	Discard 'aab', no more substrings
18	End			[]	aab	All partitions found, stop

💡 All substrings tried, all palindrome partitions collected.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 8	After Step 11	After Step 12	After Step 13	Final
path	[]	["a"]	["a", "a"]	["a", "a", "b"]	["a", "a", "b"]	["a", "a"]	["a"]	["aa"]	["aa", "b"]	["aa", "b"]	[]
res	[]	[]	[]	[]	[["a", "a", "b"]]	[["a", "a", "b"]]	[["a", "a", "b"]]	[["a", "a", "b"]]	[["a", "a", "b"]]	[["a", "a", "b"], ["aa", "b"]]	[["a", "a", "b"], ["aa", "b"]]
start	0	1	2	3	3	2	1	2	3	3	0

Key Moments - 3 Insights

Why do we backtrack by removing the last substring from path?

Because after exploring one choice fully (see Step 5 and Step 13), we remove the last substring to try other possible substrings (see Steps 6 and 14). This ensures all partitions are explored.

Why do we check if substring is palindrome before adding to path?

Only palindrome substrings are valid parts of the partition. Checking at each step (see Steps 2, 3, 4, 9, 11) avoids invalid partitions and reduces unnecessary recursion.

What happens when start index reaches the string length?

It means we have partitioned the entire string successfully (see Step 5 and Step 13). We then add the current path to results and backtrack to find other partitions.

Visual Quiz - 3 Questions

Look at the execution table at Step 4, what is the current path?

A ["a", "a", "b"]

B ["a"]

C ["a", "a"]

D []

💡 Hint

Check the 'Path (Current Partition)' column at Step 4 in the execution table.

At which step does the algorithm add the partition ["aa", "b"] to the results?

A Step 5

B Step 18

C Step 13

D Step 11

💡 Hint

Look for 'Add path to results' action with path ["aa", "b"] in the execution table.

If the input string was 'aaa', how would the path change after the first recursion?

A ["aa"]

B ["a"]

C ["a", "a"]

D ["aaa"]

💡 Hint

Check variable_tracker for path after first substring added (similar to Step 2).

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Try all substrings from current start
- Check if substring is palindrome
- If yes, add to current path
- Recurse with remaining string
- If start reaches end, add path to results
- Backtrack by removing last substring
- Explore all partitions this way

Full Transcript

Palindrome Partitioning uses backtracking to find all ways to split a string into palindrome substrings. We start with an empty path and try every substring from the current start index. If the substring is a palindrome, we add it to the path and recurse on the remaining string. When the start index reaches the string length, we add the current path to the results. Then we backtrack by removing the last substring and try other substrings. This process continues until all partitions are found. The execution table shows each step, substring chosen, palindrome check, current path, and remaining string. Variable tracker shows how path and results change. Key moments clarify why backtracking and palindrome checks are needed. Visual quizzes test understanding of path states and results addition.

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