Palindrome Partitioning Using Backtracking in DSA C - Execution Trace

Concept Flow - Palindrome Partitioning Using Backtracking

Start with empty partition

↓

Choose substring from start

↓

Check if substring is palindrome?

No→Discard substring, try next

Yes↓

Add substring to current partition

↓

Recurse for remaining string

↓

If no string left

→Save current partition as solution

↓

Backtrack: remove last substring

↩Back to choose next substring

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

Execution Sample

DSA C

void backtrack(char* s, int start) {
  if (start == strlen(s)) save_partition();
  for (int end = start; end < strlen(s); end++) {
    if (isPalindrome(s, start, end)) {
      addSubstring(s, start, end);
      backtrack(s, end + 1);
      removeLastSubstring();
    }
  }
}

This code tries all substrings starting at 'start', adds palindrome substrings to partition, recurses, then backtracks.

Execution Table

Step	Operation	Substring Chosen	Palindrome?	Current Partition	Action	Visual State
1	Choose substring s[0:0]	"a"	Yes	[]	Add 'a'	["a"]
2	Recurse from index 1			["a"]	Continue	["a"]
3	Choose substring s[1:1]	"b"	Yes	["a"]	Add 'b'	["a", "b"]
4	Recurse from index 2			["a", "b"]	Continue	["a", "b"]
5	Choose substring s[2:2]	"a"	Yes	["a", "b"]	Add 'a'	["a", "b", "a"]
6	Recurse from index 3			["a", "b", "a"]	Save partition	["a", "b", "a"]
7	Backtrack			["a", "b", "a"]	Remove 'a'	["a", "b"]
8	Backtrack			["a", "b"]	Remove 'b'	["a"]
9	Choose substring s[1:2]	"ba"	No	["a"]	Discard	["a"]
10	Backtrack			["a"]	Remove 'a'	[]
11	Choose substring s[0:1]	"ab"	No	[]	Discard	[]
12	Choose substring s[0:2]	"aba"	Yes	[]	Add 'aba'	["aba"]
13	Recurse from index 3			["aba"]	Save partition	["aba"]
14	Backtrack			["aba"]	Remove 'aba'	[]
15	End			[]	All partitions found	[]

💡 All substrings tried and all palindrome partitions saved.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 6	After Step 7	After Step 8	After Step 10	After Step 12	After Step 13	Final
start index	0	1	2	3	3	3	2	1	3	3	end of string
current partition	[]	["a"]	["a", "b"]	["a", "b", "a"]	["a", "b", "a"]	["a", "b"]	["a"]	[]	["aba"]	["aba"]	[]

Key Moments - 3 Insights

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

Because after exploring partitions with that substring, we must remove it to try other substrings starting at the same position (see steps 6 to 8 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 9).

How do we know when to save a partition?

When the start index reaches the string length, meaning the whole string is partitioned (see step 6 and 13).

Visual Quiz - 3 Questions

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

A ["a", "b"]

B ["a"]

C ["a", "b", "a"]

D []

💡 Hint

Check the 'Visual State' column at step 5 in execution_table.

At which step does the algorithm discard a non-palindrome substring?

A Step 9

B Step 12

C Step 3

D Step 1

💡 Hint

Look for 'Palindrome?' column with 'No' and 'Action' as 'Discard' in execution_table.

If the input string was "aa", how would the partitions change?

A ["a"] only

B ["a", "a"] and ["aa"]

C ["aa"] only

D No partitions

💡 Hint

Consider palindrome substrings of "aa" and how backtracking explores all partitions.

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Try all substrings from current start
- Check if substring is palindrome
- If yes, add to current partition
- Recurse on remaining string
- If end reached, save partition
- Backtrack by removing last substring
- Explore all palindrome partitions

Full Transcript

Palindrome Partitioning using backtracking tries all possible substrings starting from the current index. For each substring, it checks if it is a palindrome. If yes, it adds the substring to the current partition and recursively continues with the remaining string. When the start index reaches the end of the string, it saves the current partition as a valid solution. After recursion, it backtracks by removing the last added substring to try other possibilities. This process continues until all palindrome partitions are found.