Palindrome Partitioning Using Backtracking in DSA Javascript - 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 remaining string

→Add path to results

↓

Backtrack: remove last substring

↓

Try next substring from previous step

We try all substrings from the start, check if palindrome, add to path, recurse on rest, and backtrack to explore all partitions.

Execution Sample

DSA Javascript

function backtrack(start, path) {
  if (start === s.length) results.push([...path]);
  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.

Execution Table

Step	Operation	Substring Checked	Is Palindrome?	Path (Partitions So Far)	Action	Visual State
1	Start backtrack	-	-	[]	Try substrings from index 0	[]
2	Check substring	'a' (0-0)	Yes	[]	Add 'a' to path	['a']
3	Recurse	-	-	['a']	Try substrings from index 1	['a']
4	Check substring	'a' (1-1)	Yes	['a']	Add 'a' to path	['a', 'a']
5	Recurse	-	-	['a', 'a']	Try substrings from index 2	['a', 'a']
6	Check substring	'b' (2-2)	Yes	['a', 'a']	Add 'b' to path	['a', 'a', 'b']
7	Recurse	-	-	['a', 'a', 'b']	Try substrings from index 3	['a', 'a', 'b']
8	End reached	-	-	['a', 'a', 'b']	Add path to results	Results: [['a','a','b']]
9	Backtrack	-	-	['a', 'a', 'b']	Remove 'b'	['a', 'a']
10	Check substring	'ba' (2-3)	No	['a', 'a']	Discard substring	['a', 'a']
11	Backtrack	-	-	['a', 'a']	Remove 'a'	['a']
12	Check substring	'ab' (1-2)	No	['a']	Discard substring	['a']
13	Check substring	'aba' (1-3)	Yes	['a']	Add 'aba' to path	['a', 'aba']
14	Recurse	-	-	['a', 'aba']	Try substrings from index 4	['a', 'aba']
15	End reached	-	-	['a', 'aba']	Add path to results	Results: [['a','a','b'], ['a','aba']]
16	Backtrack	-	-	['a', 'aba']	Remove 'aba'	['a']
17	Backtrack	-	-	['a']	Remove 'a'	[]
18	Check substring	'aa' (0-1)	Yes	[]	Add 'aa' to path	['aa']
19	Recurse	-	-	['aa']	Try substrings from index 2	['aa']
20	Check substring	'b' (2-2)	Yes	['aa']	Add 'b' to path	['aa', 'b']
21	Recurse	-	-	['aa', 'b']	Try substrings from index 3	['aa', 'b']
22	End reached	-	-	['aa', 'b']	Add path to results	Results: [['a','a','b'], ['a','aba'], ['aa','b']]
23	Backtrack	-	-	['aa', 'b']	Remove 'b'	['aa']
24	Backtrack	-	-	['aa']	Remove 'aa'	[]
25	Check substring	'aab' (0-2)	No	[]	Discard substring	[]
26	Check substring	'aaba' (0-3)	No	[]	Discard substring	[]
27	End	-	-	[]	All substrings tried	Final Results: [['a','a','b'], ['a','aba'], ['aa','b']]

💡 All substrings from each start index checked; all palindrome partitions found.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 13	After Step 15	After Step 18	After Step 20	After Step 22	Final
path	[]	['a']	['a', 'a']	['a', 'a', 'b']	['a', 'a', 'b']	['a', 'aba']	['a', 'aba']	['aa']	['aa', 'b']	['aa', 'b']	[]
results	[]	[]	[]	[]	[['a','a','b']]	[['a','a','b']]	[['a','a','b'], ['a','aba']]	[['a','a','b'], ['a','aba']]	[['a','a','b'], ['a','aba']]	[['a','a','b'], ['a','aba'], ['aa','b']]	[['a','a','b'], ['a','aba'], ['aa','b']]
start	0	0	1	2	3	1	4	0	2	3	-

Key Moments - 3 Insights

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

Because after exploring all partitions starting with that substring, we must remove it to try other substrings from the previous position (see steps 8 to 9 and 15 to 16 in execution_table).

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

Only palindrome substrings can be part of the partition. Non-palindromes are discarded immediately (see step 10 and 12 where substrings are rejected).

When do we add the current path to results?

When the start index reaches the string length, meaning the whole string is partitioned (see steps 8, 15, and 22).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the path array?

A ['a', 'a']

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

C ['a']

D []

💡 Hint

Check the 'Path (Partitions So Far)' column at step 6 in execution_table.

At which step does the algorithm add the partition ['a', 'aba'] to results?

A Step 8

B Step 22

C Step 15

D Step 18

💡 Hint

Look for 'Add path to results' action with path ['a', 'aba'] in execution_table.

If the input string was 'aaa', how would the number of results change compared to the example?

A More results because more palindrome partitions exist

B Fewer results because string is shorter

C Same number of results

D No results because no palindrome substrings

💡 Hint

Consider palindrome substrings in 'aaa' and how backtracking explores all partitions.

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Try all substrings from current start index
- Check if substring is palindrome
- If yes, add to current path and recurse on remaining string
- If start reaches string end, add path to results
- Backtrack by removing last substring to explore other partitions

Full Transcript

Palindrome Partitioning Using Backtracking tries all ways to split a string into palindrome substrings. Starting from index 0, it checks every substring. If the substring is a palindrome, it adds it to the current path and recursively tries to partition the rest of the string. When the start index reaches the string length, it means a full partition is found and added to results. Then it backtracks by removing the last substring to try other options. This process repeats until all partitions are found.

Practice

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

easy

A. To split a string into all possible palindrome substrings

B. To find the longest palindrome substring in a string

C. To reverse a string using recursion

D. To count the number of palindromes in a string

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 and keep only palindrome parts.

3. Final Answer:

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

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Backtracking tries all splits keeping palindromes only [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only finds one palindrome partition
• Assuming it reverses the string

2. Which of the following is the correct way to check if a substring s.slice(start, end) is a palindrome in JavaScript?

easy

A. Check if s.slice(start, end) === s.slice(end, start).reverse()

B. Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('')

C. Check if s.slice(start, end) === s.reverse()

D. Check if s.slice(start, end) === s.split('').reverse()

Solution

1. Step 1: Extract substring correctly

   Use s.slice(start, end) to get substring from start to end-1.

2. Step 2: Check palindrome by reversing substring

   Reverse substring by splitting to array, reversing, then joining back to string.

3. Final Answer:

   Check if s.slice(start, end) === s.slice(start, end).split('').reverse().join('') -> Option B

4. Quick Check:

   Reverse substring and compare equals original [OK]

Hint: Reverse substring with split, reverse, join to check palindrome [OK]

Common Mistakes:

• Using slice with reversed indices (end before start)
• Trying to reverse string directly without split
• Comparing substring to reversed full string

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

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

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

let result = [];
backtrack('aab', 0, [], result);
console.log(result);

medium

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

B. [["aab"]]

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

D. [["aa", "ab"]]

Solution

1. Step 1: Check palindrome substrings in 'aab'

   Substrings: 'a', 'aa', 'aab', 'ab', 'b'. Palindromes are 'a', 'aa', 'b'.

2. Step 2: Backtracking builds partitions

   Partitions: ['a','a','b'] and ['aa','b'] are valid palindrome partitions.

3. Final Answer:

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

4. Quick Check:

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

Hint: Check all palindrome splits recursively to get partitions [OK]

Common Mistakes:

• Including non-palindrome substrings like 'ab'
• Missing the partition ['aa','b']
• Confusing output format with strings instead of arrays

4. Identify the bug in this backtracking code for palindrome partitioning:

function backtrack(s, start, path, result) {
  if (start > s.length) {
    result.push(path);
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    let sub = s.slice(start, end);
    if (sub === sub.split('').reverse().join('')) {
      path.push(sub);
      backtrack(s, end, path, result);
      path.pop();
    }
  }
}

medium

A. The path array should not be mutated with push and pop

B. The substring check is incorrect; should use a separate isPalindrome function

C. The base case condition should be start === s.length, not start > s.length

D. The for loop should start from end = start, not start + 1

Solution

1. Step 1: Analyze base case condition

   Base case triggers when start > s.length, but valid partitions end exactly at start === s.length.

2. Step 2: Correct base case to push result

   Change condition to start === s.length to add current path to result correctly.

3. Final Answer:

   The base case condition should be start === s.length, not start > s.length -> Option C

4. Quick Check:

   Base case triggers at string end index [OK]

Hint: Base case must match string length exactly to save partitions [OK]

Common Mistakes:

• Using > instead of === for base case
• Not pushing a copy of path (but not asked here)
• Starting loop incorrectly at start instead of start+1

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find?

hard

A. 8

B. 6

C. 4

D. 10

Solution

1. Step 1: Identify palindrome substrings in 'racecar'

   Palindromes include all single characters 'r','a','c','e','c','a','r'; 'cec' (indices 2-4); 'aceca' (1-5); 'racecar' (whole).

2. Step 2: Count all palindrome partitions

   Valid partitions: ['racecar'], ['r','aceca','r'], ['r','a','cec','a','r'], ['r','a','c','e','c','a','r'], and others. Total 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Backtracking finds 10 palindrome partitions for 'racecar' [OK]

Hint: Count all palindrome splits including nested palindromes [OK]

Common Mistakes:

• Counting only single-character partitions
• Missing larger palindrome substrings like 'aceca'
• Assuming only 1 or 2 partitions exist