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.

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

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

B. To find the longest palindrome substring in a string

C. To count the number of palindromes in a string

D. To split a string into all possible palindrome substrings

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing a string into parts where each part is a palindrome.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome parts.

3. Final Answer:

   To split a string into all possible palindrome substrings -> Option D

4. Quick Check:

   Palindrome partitioning = all palindrome splits [OK]

Hint: Backtracking explores all palindrome splits step-by-step [OK]

Common Mistakes:

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

2. Which of the following TypeScript function signatures correctly represents a backtracking function for palindrome partitioning?

easy

A. function backtrack(s: number[], start: string, path: string[], result: string[][]): string

B. function backtrack(s: string, start: number, path: string, result: string[]): boolean

C. function backtrack(s: string, start: number, path: string[], result: string[][]): void

D. function backtrack(s: string[], start: number, path: string[], result: string[][]): number

Solution

1. Step 1: Analyze parameter types

   The string to partition is 's: string', start index is 'number', path is an array of strings, and result is an array of string arrays.

2. Step 2: Check return type

   Backtracking functions usually return void because they build results by modifying the result array.

3. Final Answer:

   function backtrack(s: string, start: number, path: string[], result: string[][]): void -> Option C

4. Quick Check:

   Correct signature = function backtrack(s: string, start: number, path: string[], result: string[][]): void [OK]

Hint: Backtracking returns void and uses arrays for path and result [OK]

Common Mistakes:

• Using wrong parameter types like number[] instead of string
• Returning boolean or number instead of void
• Passing path as string instead of string[]

3. What will be the output of the following TypeScript code snippet for palindrome partitioning of string "aab"?

function isPalindrome(s: string): boolean {
  return s === s.split('').reverse().join('');
}

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

const result: string[][] = [];
backtrack("aab", 0, [], result);
console.log(result);

medium

A. [["aa", "ab"]]

B. [["a", "a", "b"], ["aa", "b"]]

C. [["a", "ab"]]

D. [["aab"]]

Solution

1. Step 1: Identify palindrome substrings in "aab"

   "a" and "aa" are palindromes; "b" is a palindrome; "ab" and "aab" are not.

2. Step 2: Trace backtracking calls

   Partitions found are ["a", "a", "b"] and ["aa", "b"] added to result.

3. Final Answer:

   [["a", "a", "b"], ["aa", "b"]] -> Option B

4. Quick Check:

   All palindrome splits of "aab" = [["a", "a", "b"], ["aa", "b"]] [OK]

Hint: Check all palindrome substrings and backtrack all splits [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the "aa" substring partition
• Returning only one partition instead of all

4. Identify the bug in the following backtracking code for palindrome partitioning and select the fix:

function isPalindrome(s: string): boolean {
  return s === s.split('').reverse().join('');
}

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

medium

A. Change condition to if (start === s.length) to stop recursion correctly

B. Change substring to slice for correct substring extraction

C. Remove path.pop() to keep all partitions

D. Change for loop to end < s.length to avoid out of bounds

Solution

1. Step 1: Analyze base case condition

   Condition 'start > s.length' allows start to be s.length + 1, which is invalid index.

2. Step 2: Correct base case for recursion end

   It should be 'start === s.length' to indicate full string processed and add path to result.

3. Final Answer:

   Change condition to if (start === s.length) to stop recursion correctly -> Option A

4. Quick Check:

   Base case must be start === s.length [OK]

Hint: Base case triggers when start equals string length [OK]

Common Mistakes:

• Using > instead of === in base case
• Removing path.pop() causing wrong partitions
• Changing substring method unnecessarily

5. Given the string "racecar", which of the following is NOT a valid palindrome partitioning produced by a backtracking algorithm?

hard

A. ["rac", "ecar"]

B. ["racecar"]

C. ["r", "a", "c", "e", "c", "a", "r"]

D. ["r", "aceca", "r"]

Solution

1. Step 1: Check palindrome validity of each substring

   "rac" and "ecar" are not palindromes; others are single letters or full palindrome.

2. Step 2: Confirm valid partitions

   Partitions with only palindrome substrings are valid; those with non-palindromes are invalid.

3. Final Answer:

   ["rac", "ecar"] -> Option A

4. Quick Check:

   Non-palindrome substrings invalidate partition [OK]

Hint: Check each substring is palindrome to validate partition [OK]

Common Mistakes:

• Assuming any split is valid without palindrome check
• Confusing full string palindrome with partial substrings
• Ignoring single character substrings as palindromes