Palindrome Partitioning Using Backtracking in DSA C++ - Execution Trace

Concept Flow - Palindrome Partitioning Using Backtracking

Start with empty partition

↓

Choose substring from start index

↓

Check if substring is palindrome?

No→Try next substring

Yes↓

Add substring to current partition

↓

Recurse from next index

↓

If start index == string length

↓

Save current partition as a solution

↓

Backtrack: remove last substring

↩Back to choose substring step

The algorithm tries all substrings from the current start index, checks if they are palindromes, adds them to the current partition, recurses forward, and backtracks to explore all partitions.

Execution Sample

DSA C++

bool isPalindrome(const string& s, int left, int right) {
  while (left < right) {
    if (s[left] != s[right]) return false;
    left++;
    right--;
  }
  return true;
}

void backtrack(string s, int start, vector<string>& current, vector<vector<string>>& result) {
  if (start == s.size()) {
    result.push_back(current);
    return;
  }
  for (int end = start; end < s.size(); end++) {
    if (isPalindrome(s, start, end)) {
      current.push_back(s.substr(start, end - start + 1));
      backtrack(s, end + 1, current, result);
      current.pop_back();
    }
  }
}

This code finds all palindrome partitions of string s by trying all substrings starting at 'start', checking palindrome, recursing, and backtracking.

Execution Table

Step	Operation	Current Start Index	Current Partition	Action	Visual State
1	Start backtrack	0	[]	Try substrings from index 0	[]
2	Check substring s[0:0] = 'a'	0	[]	Palindrome? Yes	[]
3	Add 'a' to partition	0	['a']	Recurse from index 1	['a']
4	Check substring s[1:1] = 'b'	1	['a']	Palindrome? Yes	['a']
5	Add 'b' to partition	1	['a','b']	Recurse from index 2	['a','b']
6	Check substring s[2:2] = 'a'	2	['a','b']	Palindrome? Yes	['a','b']
7	Add 'a' to partition	2	['a','b','a']	Recurse from index 3	['a','b','a']
8	Start index 3 == string length 3	3	['a','b','a']	Save partition	['a','b','a']
9	Backtrack: remove 'a'	2	['a','b']	Try next substring	['a','b']
10	No more substrings from index 2	2	['a','b']	Backtrack	['a','b']
11	Backtrack: remove 'b'	1	['a']	Try next substring	['a']
12	Check substring s[1:2] = 'ba'	1	['a']	Palindrome? No	['a']
13	No more substrings from index 1	1	['a']	Backtrack	['a']
14	Backtrack: remove 'a'	0	[]	Try next substring	[]
15	Check substring s[0:1] = 'ab'	0	[]	Palindrome? No	[]
16	Check substring s[0:2] = 'aba'	0	[]	Palindrome? Yes	[]
17	Add 'aba' to partition	0	['aba']	Recurse from index 3	['aba']
18	Start index 3 == string length 3	3	['aba']	Save partition	['aba']
19	Backtrack: remove 'aba'	0	[]	No more substrings	[]
20	End	0	[]	All partitions found	[]

💡 All substrings tried and all palindrome partitions saved.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 14	After Step 17	Final
start	0	1	2	3	2	1	0	3	0
current_partition	[]	['a']	['a','b']	['a','b','a']	['a','b']	['a']	[]	['aba']	[]
result	[]	[]	[]	[['a','b','a']]	[['a','b','a']]	[['a','b','a']]	[['a','b','a']]	[['a','b','a'], ['aba']]	[['a','b','a'], ['aba']]

Key Moments - 3 Insights

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

Because after exploring partitions starting with that substring, we must remove it to try other substrings from the same start index, as shown in steps 8 to 9 and 18 to 19 in the execution table.

Why do we check palindrome before adding substring to the partition?

To ensure only valid palindrome substrings are included. This check prevents invalid partitions and is done at every substring choice, as seen in steps 2, 4, 6, 12, and 15.

What happens when start index equals string length?

It means we have a complete partition covering the whole string, so we save the current partition as a solution, as shown in steps 8 and 18.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the current partition?

A ['a','b']

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

C ['a']

D []

💡 Hint

Check the 'Current Partition' column at step 7 in the execution table.

At which step does the algorithm save the partition ['aba']?

A Step 14

B Step 8

C Step 18

D Step 20

💡 Hint

Look for 'Save partition' action with ['aba'] in the 'Current Partition' column.

If the substring s[1:2] was palindrome, what would happen at step 12?

A Add substring to partition and recurse from index 3

B Skip substring and try next

C Backtrack immediately

D Save current partition

💡 Hint

Refer to the pattern of actions when palindrome check is Yes in the execution table steps 2-7.

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Try all substrings from current start index
- Check if substring is palindrome
- If yes, add to current partition and recurse
- If start == string length, save partition
- Backtrack by removing last substring to try others

Full Transcript

This visualization shows how palindrome partitioning uses backtracking. We start with an empty partition and try all substrings from the current start index. For each substring, we check if it is a palindrome. If yes, we add it to the current partition and recurse from the next index. When the start index reaches the string length, we save the current partition as a valid solution. Then we backtrack by removing the last substring to explore other partitions. The execution table traces each step, showing substring checks, partition changes, recursion, and backtracking. The variable tracker shows how the start index, current partition, and result list change over time. Key moments clarify why palindrome checks happen before adding substrings, why backtracking is needed, and when partitions are saved. The quiz tests understanding of partition states and actions at specific steps.

Practice

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

easy

A. To split s into 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 using recursion

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 partitions and keeps only those where every substring is a palindrome.

3. Final Answer:

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

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Remember: partition means split into palindrome parts [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking it counts palindromes instead of partitioning
• Assuming it reverses the string

2. Which of the following is the correct base case check in a backtracking function for palindrome partitioning of string s starting at index start?

easy

A. if (start == s.length()) add current partition to result;

B. if (start > s.length()) return false;

C. if (start == s.length()) return true;

D. if (start < 0) return false;

Solution

1. Step 1: Understand base case in backtracking

   The base case occurs when the start index reaches the end of the string, meaning a full partition is formed.

2. Step 2: What to do at base case

   At this point, the current partition is a valid palindrome partition and should be added to the result list.

3. Final Answer:

   if (start == s.length()) add current partition to result; -> Option A

4. Quick Check:

   Base case adds partition when start reaches string end [OK]

Hint: Base case: start at string end means add partition [OK]

Common Mistakes:

• Returning true/false instead of adding partition
• Checking start > length instead of == length
• Using invalid index checks like start < 0

3. What is the output of the following C++ code snippet for palindrome partitioning?

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        string rev = sub;
        reverse(rev.begin(), rev.end());
        if (sub == rev) {
            path.push_back(sub);
            backtrack(s, end + 1, path, res);
            path.pop_back();
        }
    }
}

int main() {
    string s = "aab";
    vector res;
    vector<string> path;
    backtrack(s, 0, path, res);
    for (auto &v : res) {
        for (auto &str : v) cout << str << " ";
        cout << endl;
    }
    return 0;
}

medium

A. a a b \naab \naa b

B. a a b \naab

C. a a b \naa b

D. a a b

Solution

1. Step 1: Trace palindrome partitions of "aab"

   Possible palindrome partitions are ["a", "a", "b"] and ["aa", "b"].

2. Step 2: Check output format

   The code prints each partition on a new line with substrings separated by spaces, so output lines are "a a b" and "aa b".

3. Final Answer:

   a a b \naa b -> Option C

4. Quick Check:

   Partitions = ["a","a","b"], ["aa","b"] [OK]

Hint: List all palindrome splits, print each partition line [OK]

Common Mistakes:

• Missing the "aa" substring partition
• Printing partitions in wrong order
• Confusing substring boundaries

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

void backtrack(string s, int start, vector<string>& path, vector& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }
    for (int end = start; end < s.size(); ++end) {
        string sub = s.substr(start, end - start + 1);
        if (isPalindrome(sub)) {
            path.push_back(sub);
            backtrack(s, end, path, res);  // Bug here
            path.pop_back();
        }
    }
}

medium

A. The substring extraction is incorrect

B. The recursive call should use end + 1 instead of end

C. The base case condition is wrong

D. The palindrome check function is missing

Solution

1. Step 1: Analyze recursive call index

   The recursive call uses end as the next start index, but it should move past the current substring.

2. Step 2: Correct index to avoid infinite loop

   Using end + 1 ensures the next substring starts after the current one, preventing repeated processing.

3. Final Answer:

   The recursive call should use end + 1 instead of end -> Option B

4. Quick Check:

   Next start index = end + 1 to avoid overlap [OK]

Hint: Next start index must skip current substring end [OK]

Common Mistakes:

• Using end instead of end + 1 causes infinite recursion
• Ignoring base case correctness
• Assuming substring extraction is wrong

5. Given the string s = "racecarannakayak", how many palindrome partitions can be formed using backtracking? (Assume all partitions are valid palindrome splits.)

hard

A. 5

B. 12

C. 10

D. 8

Solution

1. Step 1: Identify palindromic substrings in s

   Substrings like "racecar", "anna", "kayak" are palindromes. Smaller palindromes like "a", "c", "r" also exist.

2. Step 2: Count partitions using backtracking

   Backtracking explores all splits where each substring is palindrome. For this string, there are 8 valid partitions combining these palindromes.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Backtracking counts 8 palindrome partitions for given string [OK]

Hint: Count all palindrome splits including big and small palindromes [OK]

Common Mistakes:

• Counting only large palindromes
• Missing smaller palindrome partitions
• Assuming fewer partitions than actual