Palindrome Partitioning Using Backtracking in DSA Java - Execution Trace

Concept Flow - Palindrome Partitioning Using Backtracking

Start with empty partition

↓

Choose substring from start

↓

Check if substring is palindrome

Yes No↓

Add substring to partition

↓

Recurse with remaining string

↓

If no string left

↓

Save current partition

↓

Backtrack: remove last substring

↩Back to choose next substring

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

Execution Sample

DSA Java

void backtrack(String s, int start, List<String> current, List<List<String>> result) {
  if (start == s.length()) {
    result.add(new ArrayList<>(current));
    return;
  }
  for (int end = start; end < s.length(); end++) {
    if (isPalindrome(s, start, end)) {
      current.add(s.substring(start, end + 1));
      backtrack(s, end + 1, current, result);
      current.remove(current.size() - 1);
    }
  }
}

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

Execution Table

Step	Operation	Substring Chosen	Is Palindrome?	Current Partition	Action	Visual State
1	Start			[]	Begin backtracking at index 0	[]
2	Choose substring	"a" (0-0)	Yes	[]	Add "a" to partition	["a"]
3	Recurse			["a"]	Backtrack from index 1	["a"]
4	Choose substring	"b" (1-1)	Yes	["a"]	Add "b" to partition	["a", "b"]
5	Recurse			["a", "b"]	Backtrack from index 2	["a", "b"]
6	Choose substring	"c" (2-2)	Yes	["a", "b"]	Add "c" to partition	["a", "b", "c"]
7	Recurse			["a", "b", "c"]	Reached end, save partition	[["a", "b", "c"]]
8	Backtrack			["a", "b", "c"]	Remove "c"	["a", "b"]
9	Backtrack			["a", "b"]	Remove "b"	["a"]
10	Choose substring	"bc" (1-2)	No	["a"]	Discard substring	["a"]
11	Backtrack			["a"]	Remove "a"	[]
12	Choose substring	"ab" (0-1)	No	[]	Discard substring	[]
13	Choose substring	"abc" (0-2)	No	[]	Discard substring	[]
14	End			[]	All partitions found	[["a", "b", "c"]]

💡 All substrings tried, backtracked fully, all palindrome partitions collected.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	After Step 11	Final
start	0	1	2	3	3	3	3	0	3
current partition	[]	["a"]	["a", "b"]	["a", "b", "c"]	["a", "b", "c"]	["a", "b"]	["a"]	[]	[]
result	[]	[]	[]	[]	[["a", "b", "c"]]	[["a", "b", "c"]]	[["a", "b", "c"]]	[["a", "b", "c"]]	[["a", "b", "c"]]

Key Moments - 3 Insights

Why do we remove the last substring after recursion?

Because after exploring partitions with that substring, we must backtrack to try other substrings. See steps 7 to 9 in execution_table where "c" and "b" are removed.

Why do we check if substring is palindrome before adding?

Only palindrome substrings can be part of the partition. Non-palindromes are discarded immediately (step 10). This avoids invalid partitions.

What happens when start reaches the string length?

It means we have partitioned the whole string. We save the current partition as a valid result (step 7).

Visual Quiz - 3 Questions

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

A ["a", "b", "c"]

B ["a", "b"]

C ["a"]

D []

💡 Hint

Check the 'Current Partition' column at step 6 in execution_table.

At which step does the algorithm backtrack by removing "b"?

A Step 8

B Step 10

C Step 9

D Step 11

💡 Hint

Look for 'Remove "b"' in the 'Action' column in execution_table.

If the substring "bc" was palindrome, what would change in the execution_table?

A Step 10 would discard "bc" as usual

B Step 10 would add "bc" to partition and recurse

C Step 11 would remove "bc" instead of "a"

D No change, since "bc" is not chosen

💡 Hint

Check step 10 where "bc" is currently discarded; if palindrome, it would be added and recurse.

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 on remaining string
- If start reaches string end, save current partition
- Backtrack by removing last substring to try other options

Full Transcript

Palindrome Partitioning Using Backtracking tries all ways to split a string into palindrome substrings. Starting from index 0, it picks substrings, checks if they are palindrome, and if yes, adds them to the current partition list. Then it recursively processes the rest of the string. When the start index reaches the string length, it means a full partition is found and saved. After recursion, it removes the last substring to backtrack and try other substrings. This process continues until all partitions are found. The execution table shows each step, substring chosen, palindrome check, current partition, and actions like add, recurse, backtrack, or discard. Key moments include why backtracking is needed, why palindrome check is done before adding, and what happens when the start index reaches the string length.

Practice

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

easy

A. To count the number of palindromes in a string

B. To find the longest palindrome substring in a string

C. To split a string into all possible palindrome substrings

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

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 C

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Backtracking explores all palindrome splits [OK]

Common Mistakes:

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

2. Which of the following is the correct Java method signature for a backtracking function that partitions a string into palindromes?

easy

A. boolean backtrack(String s, int start, List<String> current)

B. void backtrack(String s, int start, List result, List<String> current)

C. int backtrack(String s, int start, List<String> result)

D. String backtrack(String s, int start, List result)

Solution

1. Step 1: Analyze method parameters

   The method needs the string, current start index, a list to store all partitions, and the current partition path.

2. Step 2: Check return type

   Backtracking methods usually return void because they build results via parameters.

3. Final Answer:

   void backtrack(String s, int start, List result, List<String> current) -> Option B

4. Quick Check:

   Backtracking method returns void and uses lists [OK]

Hint: Backtracking returns void and uses lists for results [OK]

Common Mistakes:

• Using wrong return type like int or boolean
• Missing current partition list parameter
• Returning String instead of void

3. What will be the output partitions for the input string "aab" using palindrome partitioning?

medium

A. [["aab"]]

B. [["aa", "ab"]]

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

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

Solution

1. Step 1: Identify palindrome substrings

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

2. Step 2: List all palindrome partitions

   Partitions are ["a", "a", "b"] and ["aa", "b"].

3. Final Answer:

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

4. Quick Check:

   Only palindrome splits included [OK]

Hint: Check each substring palindrome before partitioning [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the partition with "aa"
• Returning only one partition

4. Identify the error in this Java backtracking snippet for palindrome partitioning:

void backtrack(String s, int start, List result, List<String> current) {
  if (start == s.length()) {
    result.add(current);
    return;
  }
  for (int end = start; end < s.length(); end++) {
    if (isPalindrome(s, start, end)) {
      current.add(s.substring(start, end + 1));
      backtrack(s, end + 1, result, current);
      current.remove(current.size());
    }
  }
}

medium

A. Incorrect removal index in current.remove()

B. Missing base case for empty string

C. Wrong substring indices in s.substring()

D. Backtracking call uses wrong start index

Solution

1. Step 1: Check removal from current list

   List indices start at 0, so removing at current.size() causes IndexOutOfBoundsException.

2. Step 2: Correct removal index

   Should remove last element with current.remove(current.size() - 1).

3. Final Answer:

   Incorrect removal index in current.remove() -> Option A

4. Quick Check:

   Remove last element with size()-1 [OK]

Hint: Remove last added element with size()-1 index [OK]

Common Mistakes:

• Removing element at size() instead of size()-1
• Confusing substring indices
• Incorrect recursive call start index

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

hard

A. 6

B. 8

C. 4

D. 10

Solution

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

   Palindromes include "r", "a", "c", "e", "cec", "aceca", "racecar" and their combinations.

2. Step 2: Count all palindrome partitions

   Partitions are:
   ["racecar"],
   ["r", "aceca", "r"],
   ["r", "a", "cec", "a", "r"],
   ["r", "a", "c", "e", "c", "a", "r"],
   and others including splits like ["r", "a", "c", "ec", "a", "r"] are invalid because "ec" is not palindrome.
   Counting all valid partitions, the total is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count all palindrome partitions = 6 [OK]

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

Common Mistakes:

• Counting only single-character partitions
• Missing longer palindrome substrings
• Double counting partitions