Palindrome Partitioning Using Backtracking in DSA Go - 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 string empty

→Save current partition as solution

↓

Backtrack: remove last substring

↩Back to choose next substring

Start from the beginning, pick substrings, check palindrome, recurse on remainder, save complete partitions, then backtrack to try other options.

Execution Sample

DSA Go

func partition(s string) [][]string {
  var res [][]string
  var path []string
  var backtrack func(start int)

  backtrack = func(start int) {
    if start == len(s) { res = append(res, append([]string{}, path...)); return }
    for end := start; end < len(s); end++ {
      if isPalindrome(s, start, end) {
        path = append(path, s[start:end+1])
        backtrack(end+1)
        path = path[:len(path)-1]
      }
    }
  }
  backtrack(0)
  return res
}

This code finds all palindrome partitions of a string by trying all substrings, checking palindrome, and backtracking.

Execution Table

Step	Operation	Current Substring	Is Palindrome?	Action	Current Partition	Remaining String
1	Start backtrack			Start at index 0	[]	aab
2	Check substring	a	Yes	Add 'a' to partition	['a']	ab
3	Recurse			Backtrack from index 1	['a']	ab
4	Check substring	a	Yes	Add 'a' to partition	['a', 'a']	b
5	Recurse			Backtrack from index 2	['a', 'a']	b
6	Check substring	b	Yes	Add 'b' to partition	['a', 'a', 'b']
7	Recurse			Index 3 == len(s), save partition	['a', 'a', 'b']
8	Backtrack			Remove 'b'	['a', 'a']	b
9	Check substring	ab	No	Discard substring	['a', 'a']	b
10	Backtrack			Remove 'a'	['a']	ab
11	Check substring	ab	No	Discard substring	['a']	ab
12	Check substring	aab	No	Discard substring	['a']	ab
13	Backtrack			Remove 'a'	[]	aab
14	Check substring	aa	Yes	Add 'aa' to partition	['aa']	b
15	Recurse			Backtrack from index 2	['aa']	b
16	Check substring	b	Yes	Add 'b' to partition	['aa', 'b']
17	Recurse			Index 3 == len(s), save partition	['aa', 'b']
18	Backtrack			Remove 'b'	['aa']	b
19	Backtrack			Remove 'aa'	[]	aab
20	Check substring	aab	No	Discard substring	[]	aab
21	End			All substrings checked	[]	aab

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 14	After Step 16	Final
path	[]	['a']	['a', 'a']	['a', 'a', 'b']	['a', 'a', 'b']	['a', 'a']	['aa']	['aa', 'b']	[]
start index	0	1	2	3	3	2	2	3	N/A
res (partitions)	[]	[]	[]	[]	[['a','a','b']]	[['a','a','b']]	[['a','a','b']]	[['a','a','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 with the last substring, we must remove it to try other substrings starting at the same position, as shown in steps 7 to 8 and 17 to 18.

Why do we check if the substring is a palindrome before adding it?

Only palindrome substrings can be part of the final partition. Steps 2, 4, 6 show adding substrings only after palindrome check; non-palindromes are discarded (steps 9, 11, 12).

What happens when the start index reaches the string length?

It means we have a complete partition covering the whole string, so we save it as a solution (step 7 and 17).

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the current partition?

A ['a', 'a', 'b']

B ['a', 'a']

C ['a']

D []

💡 Hint

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

At which step does the algorithm save the partition ['aa', 'b']?

A Step 7

B Step 17

C Step 14

D Step 20

💡 Hint

Look for 'save partition' action with ['aa', 'b'] in the Current Partition column.

If the substring 'aab' was palindrome, how would the execution table change?

A It would add ['aab'] as a partition at step 20

B It would discard 'aab' at step 20

C It would add ['a', 'a', 'b'] again

D No change in the table

💡 Hint

Step 20 currently discards 'aab'; if palindrome, it would add it to partitions.

Concept Snapshot

Palindrome Partitioning Using Backtracking:
- Start from index 0
- Choose substrings and check palindrome
- If palindrome, add to current partition
- Recurse for remaining string
- If end reached, save partition
- Backtrack to try other substrings
- Repeat until all partitions found

Full Transcript

This visualization shows how palindrome partitioning uses backtracking. We start with an empty partition and try all substrings from the start index. Each substring is checked if it is a palindrome. If yes, it is added to the current partition and the function recurses on the remaining string. When the start index reaches the string length, the current partition is saved as a valid solution. Then the algorithm backtracks by removing the last substring to try other options. This process repeats until all palindrome partitions are found. The execution table traces each step, showing substring checks, palindrome decisions, partition updates, and backtracking. The variable tracker shows how the current partition and results evolve. Key moments clarify why backtracking is needed, why palindrome checks matter, and what happens at the end of the string. The quiz tests understanding of partition states and saving steps.

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 reverse a string using recursion

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 tries all splits to find palindrome partitions [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking it only finds one partition instead of all
• Mixing palindrome check with string reversal

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

easy

A. func backtrack(s string, start int, path []string, result *[][]string)

B. func backtrack(s int, start string, path []int, result [][]string)

C. func backtrack(s string, path int, start []string, result [][]string)

D. func backtrack(s []string, start int, path string, result *[][]string)

Solution

1. Step 1: Analyze parameter types

   The string to partition is 's string', start index is 'int', current path is '[]string', and result is pointer to slice of slices of strings.

2. Step 2: Match correct signature

   func backtrack(s string, start int, path []string, result *[][]string) matches all types correctly for backtracking palindrome partitioning.

3. Final Answer:

   func backtrack(s string, start int, path []string, result *[][]string) -> Option A

4. Quick Check:

   Correct parameter types = func backtrack(s string, start int, path []string, result *[][]string) [OK]

Hint: Check parameter types: string, int, slice, pointer to result [OK]

Common Mistakes:

• Mixing parameter order or types
• Using non-pointer for result when modification needed
• Confusing path and start parameter types

3. What is the output of the following Go code snippet?

package main
import "fmt"

func isPalindrome(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}

func backtrack(s string, start int, path []string, result *[][]string) {
    if start == len(s) {
        temp := make([]string, len(path))
        copy(temp, path)
        *result = append(*result, temp)
        return
    }
    for end := start + 1; end <= len(s); end++ {
        if isPalindrome(s[start:end]) {
            backtrack(s, end, append(path, s[start:end]), result)
        }
    }
}

func partition(s string) [][]string {
    var result [][]string
    backtrack(s, 0, []string{}, &result)
    return result
}

func main() {
    res := partition("aab")
    fmt.Println(res)
}

medium

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

B. [["aab"]]

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

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

Solution

1. Step 1: Check palindrome substrings of "aab"

   "a" is palindrome, "aa" is palindrome, "b" is palindrome, "ab" is not palindrome.

2. Step 2: Backtracking partitions

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

3. Final Answer:

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

4. Quick Check:

   All palindrome partitions = [["a", "a", "b"], ["aa", "b"]] [OK]

Hint: Check all palindrome splits, ignore non-palindromes [OK]

Common Mistakes:

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

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

func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-i] {
            return false
        }
    }
    return true
}

medium

A. Missing return statement

B. Incorrect loop condition, should be i <= len(s)/2

C. Index out of range error due to s[len(s)-i]

D. No bug, code is correct

Solution

1. Step 1: Analyze index usage in palindrome check

   Index s[len(s)-i] is out of range because last index is len(s)-1, not len(s).

2. Step 2: Correct index to s[len(s)-1-i]

   Subtract 1 from len(s) to avoid out of range error.

3. Final Answer:

   Index out of range error due to s[len(s)-i] -> Option C

4. Quick Check:

   Index error = Index out of range error due to s[len(s)-i] [OK]

Hint: Last index is len(s)-1, not len(s) [OK]

Common Mistakes:

• Using len(s)-i instead of len(s)-1-i
• Ignoring index out of range panic
• Assuming loop condition fixes index error

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm find? Consider all possible partitions where each substring is a palindrome.

hard

A. 4

B. 8

C. 6

D. 10

Solution

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

   Palindromes include all single characters, "cec" (indices 2-4), "aceca" (1-5), "racecar" (0-6).

2. Step 2: List all palindrome partitions

   Partitions are: ["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"], ["r", "a", "c", "ece", "a", "r"], ["r", "a", "c", "e", "c", "a", "r"] (already counted), and others totaling 8 unique partitions.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Count all palindrome partitions = 8 [OK]

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

Common Mistakes:

• Counting only single character partitions
• Missing longer palindrome substrings like "aceca"
• Including invalid partitions like "ece"