Palindrome Partitioning Using Backtracking in DSA Go

Mental Model

We try to split a string into parts where each part reads the same forwards and backwards. We explore all ways to do this by trying each possible cut and going back if it doesn't work.

Analogy: Imagine cutting a ribbon into pieces where each piece is a perfect mirror image of itself. You try cutting at different points, and if a piece isn't a mirror, you undo the cut and try another place.

s = "a b a c"
Indices: 0 1 2 3
Partitions try: [a] [b a c], [a b] [a c], [a b a] [c], etc.
Each [] is a substring checked if palindrome.

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" into palindrome parts

Step 1: Check substring from index 0 to 0: "a" is palindrome, choose it

["a"] + remaining "ab" to partition

Why: Start with smallest palindrome to build partitions

Step 2: Check substring from index 1 to 1: "a" is palindrome, choose it

["a", "a"] + remaining "b" to partition

Why: Continue partitioning remaining string

Step 3: Check substring from index 2 to 2: "b" is palindrome, choose it

["a", "a", "b"] no remaining string

Why: Reached end with all palindrome parts, save this partition

Step 4: Backtrack to index 1, try substring 1 to 2: "ab" is not palindrome, discard

["a"] + remaining "ab" but no valid partition from index 1 to 2

Why: Discard invalid palindrome to try other partitions

Step 5: Backtrack to index 0, try substring 0 to 1: "aa" is palindrome, choose it

["aa"] + remaining "b" to partition

Why: Try longer palindrome from start

Step 6: Check substring from index 2 to 2: "b" is palindrome, choose it

["aa", "b"] no remaining string

Why: Reached end with all palindrome parts, save this partition

Result:

["a", "a", "b"]
["aa", "b"]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func isPalindrome(s string, start, end int) bool {
	for start < end {
		if s[start] != s[end] {
			return false
		}
		start++
		end--
	}
	return true
}

func backtrack(s string, start int, path []string, result *[][]string) {
	if start == len(s) {
		// reached end, save current partition
		temp := make([]string, len(path))
		copy(temp, path)
		*result = append(*result, temp)
		return
	}

	for end := start; end < len(s); end++ {
		if isPalindrome(s, start, end) {
			// choose substring s[start:end+1]
			path = append(path, s[start:end+1])
			backtrack(s, end+1, path, result) // explore further
			path = path[:len(path)-1] // backtrack
		}
	}
}

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

func main() {
	input := "aab"
	res := partition(input)
	for _, partition := range res {
		fmt.Println(partition)
	}
}

for start < end { if s[start] != s[end] { return false } start++; end-- }

check if substring is palindrome by comparing characters from both ends

if start == len(s) { copy path to result; return }

if reached end of string, save current palindrome partition

for end := start; end < len(s); end++ { if isPalindrome(s, start, end) { ... } }

try all substrings starting at 'start' and choose palindromes

path = append(path, s[start:end+1]); backtrack(s, end+1, path, result); path = path[:len(path)-1]

choose substring, recurse to partition rest, then undo choice (backtrack)

Output

[a a b]

[aa b]

Complexity Analysis

Time: O(n * 2^n) because each character can be a cut or not, and palindrome checks take O(n)

Space: O(n) for recursion stack and path storage

vs Alternative: Naive approach tries all partitions without pruning; backtracking prunes by checking palindrome early, reducing unnecessary work

Edge Cases

empty string

returns empty list of partitions

DSA Go

if start == len(s) { ... } in backtrack function

string with all same characters, e.g. "aaa"

returns all possible palindrome partitions including single chars and longer palindromes

DSA Go

isPalindrome function correctly identifies palindromes

string with no palindrome longer than 1, e.g. "abc"

returns partitions with single characters only

DSA Go

isPalindrome function returns false for longer substrings

When to Use This Pattern

When asked to find all ways to split a string into palindrome parts, use backtracking to explore all partitions and prune by palindrome checks.

Common Mistakes

Mistake: Not backtracking (undoing) after recursive call, causing path to grow incorrectly
Fix: Remove last added substring from path after recursive call to restore state

Mistake: Checking palindrome inefficiently inside recursion multiple times
Fix: Use a helper function to check palindrome quickly and only when needed

Summary

Splits a string into all possible palindrome partitions using backtracking.

Use when you need to find all palindrome-based partitions of a string.

Try every cut, check palindrome, and backtrack to explore all valid partitions.

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"