Palindrome Partitioning Using Backtracking in DSA Typescript - Execution Trace

Concept Flow - Palindrome Partitioning Using Backtracking

Start with empty partition

↓

Choose substring from current index

↓

Check if substring is palindrome?

No→Discard substring, try next

Yes↓

Add substring to current partition

↓

Recurse from next index

↓

If end of string reached

↓

Save current partition

↓

Backtrack: remove last substring

↩Back to choose next substring

We try all substrings from the current position, check if palindrome, add to partition, recurse, and backtrack to explore all partitions.

Execution Sample

DSA Typescript

function backtrack(start: number, path: string[]) {
  if (start === s.length) {
    result.push([...path]);
    return;
  }
  for (let end = start; end < s.length; end++) {
    if (isPalindrome(s, start, end)) {
      path.push(s.substring(start, end + 1));
      backtrack(end + 1, path);
      path.pop();
    }
  }
}

This code tries all substrings starting at 'start', adds palindrome substrings to path, recurses, and backtracks to find all palindrome partitions.

Execution Table

Step	Operation	Current Index	Substring Checked	Is Palindrome?	Current Partition	Action
1	Start backtrack	0	-	-	[]	Begin with empty partition
2	Check substring	0	a	Yes	[]	Add 'a' to partition
3	Recurse	1	-	-	['a']	Go deeper from index 1
4	Check substring	1	a	Yes	['a']	Add 'a' to partition
5	Recurse	2	-	-	['a','a']	Go deeper from index 2
6	Check substring	2	b	Yes	['a','a']	Add 'b' to partition
7	Recurse	3	-	-	['a','a','b']	Reached end, save partition
8	Backtrack	3	-	-	['a','a','b']	Remove 'b'
9	Backtrack	2	-	-	['a','a']	Remove 'a'
10	Check substring	1	ab	No	['a']	Discard 'ab'
11	Backtrack	1	-	-	['a']	Remove 'a'
12	Check substring	0	aa	Yes	[]	Add 'aa' to partition
13	Recurse	2	-	-	['aa']	Go deeper from index 2
14	Check substring	2	b	Yes	['aa']	Add 'b' to partition
15	Recurse	3	-	-	['aa','b']	Reached end, save partition
16	Backtrack	3	-	-	['aa','b']	Remove 'b'
17	Backtrack	2	-	-	['aa']	Remove 'aa'
18	Check substring	0	aab	No	[]	Discard 'aab'
19	End	-	-	-	[]	All partitions found, stop

💡 Reached end of string at step 7 and 15, saved partitions; no more substrings to check at step 19

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 8	After Step 12	After Step 15	Final
start	0	1	2	3	3	2	3	-
path	[]	['a']	['a','a']	['a','a','b']	['a','a']	['aa']	['aa','b']	[]
result	[]	[]	[]	[['a','a','b']]	[['a','a','b']]	[['a','a','b']]	[['a','a','b'], ['aa','b']]	[['a','a','b'], ['aa','b']]

Key Moments - 3 Insights

Why do we backtrack by removing the last substring after recursion?

Because after exploring partitions including that substring, we must remove it to try other substrings starting at the same index (see steps 7 to 8 and 15 to 16 in execution_table).

Why do we only add substrings that are palindromes?

Because the problem requires partitions where every substring is a palindrome. Non-palindromes are discarded immediately (see step 10 and 18).

How do we know when to save the current partition?

When the current index reaches the end of the string (step 7 and 15), the current partition is complete and saved.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current partition at step 5?

A ['a']

B ['a','a']

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

D []

💡 Hint

Check the 'Current Partition' column at step 5 in execution_table

At which step does the algorithm discard the substring 'ab'?

A Step 10

B Step 12

C Step 18

D Step 2

💡 Hint

Look for 'Discard' action and substring 'ab' in execution_table

If the input string was 'aaa', how would the number of saved partitions change compared to the current execution?

A It would increase

B It would decrease

C It would stay the same

D It would be zero

💡 Hint

Consider more palindrome substrings possible in 'aaa' compared to 'aab' in variable_tracker

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Try all substrings from current index
- Check if substring is palindrome
- If yes, add to current partition and recurse
- If reach end, save partition
- Backtrack by removing last substring to try others
- Explore all palindrome partitions of the string

Full Transcript

This visualization shows how palindrome partitioning uses backtracking. We start from index 0 with an empty partition. We check every substring from the current index. If the substring is a palindrome, we add it to the current partition and recurse from the next index. When we reach the end of the string, we save the current partition as a valid solution. Then we backtrack by removing the last substring to try other substrings. Non-palindrome substrings are discarded immediately. This process continues until all partitions are found. The execution table tracks each step, substring checked, palindrome check, current partition, and actions taken. The variable tracker shows how the start index, current path, and result list change over time. Key moments clarify why backtracking is needed, why only palindromes are added, and when partitions are saved. The quiz tests understanding of partition states, substring discards, and effects of input changes.