Palindrome Partitioning Using Backtracking in DSA C#

Mental Model

We try to split a string into parts where each part reads the same forwards and backwards. We explore all ways by choosing parts step-by-step and going back if a choice doesn't work.

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

s = "a b a c"
Partitions: []
Try cutting:
[a] [b a c]
[a b] [a c]
[a b a] [c]
Each [] is a substring to check palindrome.

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" so every part is a palindrome

Step 1: Check substring "a" (index 0 to 0), it is palindrome, add to current partition

Partitions: ["a"]
Remaining string: "ab"

Why: Start with smallest piece to build partitions

Step 2: Check substring "a" (index 1 to 1), palindrome, add to partition

Partitions: ["a", "a"]
Remaining string: "b"

Why: Continue partitioning next part

Step 3: Check substring "b" (index 2 to 2), palindrome, add to partition

Partitions: ["a", "a", "b"]
Remaining string: "" (empty)

Why: Reached end, save this partition as one solution

Step 4: Backtrack: remove last "b", try next substring from index 1

Partitions: ["a", "a"]
Remaining string: "b"

Why: Explore other partitions

Step 5: Backtrack: remove last "a", try substring "ab" (index 1 to 2), not palindrome, discard

Partitions: ["a"]
Remaining string: "ab"

Why: Discard invalid partition, try next

Step 6: Check substring "aa" (index 0 to 1), palindrome, add to partition

Partitions: ["aa"]
Remaining string: "b"

Why: Try bigger palindrome from start

Step 7: Check substring "b" (index 2 to 2), palindrome, add to partition

Partitions: ["aa", "b"]
Remaining string: "" (empty)

Why: Reached end, save this partition as another solution

Result:

Partitions found:
["a", "a", "b"]
["aa", "b"]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class PalindromePartitioning {
    public static IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result);
        return result;
    }

    private static void Backtrack(string s, int start, List<string> current, IList<IList<string>> result) {
        if (start == s.Length) {
            result.Add(new List<string>(current));
            return;
        }

        for (int end = start; end < s.Length; end++) {
            if (IsPalindrome(s, start, end)) {
                current.Add(s.Substring(start, end - start + 1));
                Backtrack(s, end + 1, current, result);
                current.RemoveAt(current.Count - 1);
            }
        }
    }

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

    static void Main() {
        string input = "aab";
        var partitions = Partition(input);
        foreach (var partition in partitions) {
            Console.WriteLine(string.Join(", ", partition));
        }
    }
}

if (start == s.Length) {

Reached end of string, save current partition as a valid solution

for (int end = start; end < s.Length; end++) {

Try all possible substring ends from current start

if (IsPalindrome(s, start, end)) {

Check if current substring is palindrome before choosing it

current.Add(s.Substring(start, end - start + 1));

Add palindrome substring to current partition

Backtrack(s, end + 1, current, result);

Recurse to partition remaining string after current substring

current.RemoveAt(current.Count - 1);

Backtrack: remove last substring to try other partitions

while (left < right) { if (s[left] != s[right]) return false; left++; right--; }

Check palindrome by comparing characters from both ends

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 current partition storage

vs Alternative: Naive approach tries all partitions without pruning; backtracking prunes by checking palindrome early, saving time

Edge Cases

empty string

returns a list containing one empty partition [[]]

DSA C#

if (start == s.Length) { result.Add(new List<string>(current)); return; }

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

returns all possible palindrome partitions including single chars and bigger palindromes

DSA C#

if (IsPalindrome(s, start, end)) { ... }

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

returns partitions with single characters only

DSA C#

if (IsPalindrome(s, start, end)) { ... }

When to Use This Pattern

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

Common Mistakes

Mistake: Not backtracking (removing last added substring) after recursive call, causing incorrect partitions
Fix: Always remove last substring after recursion to explore other partitions

Mistake: Checking palindrome inefficiently or incorrectly
Fix: Use two-pointer approach to check palindrome in O(length) time

Summary

It finds all ways to split a string into palindrome substrings.

Use it when you need every palindrome partition of a string.

The key is to try each cut, check palindrome, and backtrack to explore all options.

Practice

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

easy

A. To find the longest palindrome substring in a string

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

C. To split a string into all possible palindrome substrings

D. To count the number of palindromes in a string

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 = all palindrome splits [OK]

Hint: Backtracking explores all palindrome splits of the string [OK]

Common Mistakes:

• Confusing palindrome partitioning with finding longest palindrome
• Thinking palindrome partitioning only counts palindromes
• Assuming palindrome partitioning reverses the string

2. Which of the following C# method signatures is correct for a backtracking function that partitions a string into palindromes?

easy

A. string Backtrack(string s, int start, List<string> currentPartition, List result)

B. int Backtrack(string s, int start, List<string> currentPartition)

C. bool Backtrack(string s, int start, List<string> currentPartition, List result)

D. void Backtrack(string s, int start, List<string> currentPartition, List result)

Solution

1. Step 1: Understand backtracking method requirements

   The method should explore partitions and store results, so it returns void and uses parameters to track state.

2. Step 2: Check method signatures

   void Backtrack(string s, int start, List<string> currentPartition, List result) returns void and takes parameters for string, start index, current partition, and result list, matching backtracking needs.

3. Final Answer:

   void Backtrack(string s, int start, List<string> currentPartition, List result) -> Option D

4. Quick Check:

   Backtracking method returns void with state parameters [OK]

Hint: Backtracking methods usually return void and use parameters to track state [OK]

Common Mistakes:

• Using return types other than void for backtracking
• Missing the result list parameter to store partitions
• Confusing return type with boolean or string

3. What will be the output of the following C# code snippet?

var result = new List();
Backtrack("aab", 0, new List<string>(), result);
Console.WriteLine(result.Count);

Assuming Backtrack partitions the string into all palindrome substrings correctly.

medium

A. 2

B. 3

C. 1

D. 4

Solution

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

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

2. Step 2: Count all palindrome partitions

   There are 2 partitions, so result.Count will be 2 after backtracking.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Palindrome partitions of "aab" = 2 [OK]

Hint: Count all palindrome partitions generated by backtracking [OK]

Common Mistakes:

• Counting substrings instead of partitions
• Forgetting "aa" is a palindrome
• Assuming single partition only

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

void Backtrack(string s, int start, List<string> current, List result) {
  if (start == s.Length) {
    result.Add(new List<string>(current));
    return;
  }
  for (int end = start; end < s.Length; end++) {
    if (IsPalindrome(s, start, end)) {
      current.Add(s.Substring(start, end - start));
      Backtrack(s, end + 1, current, result);
      current.RemoveAt(current.Count - 1);
    }
  }
}

medium

A. Base case condition should be start > s.Length

B. Substring length calculation is incorrect

C. RemoveAt should remove from index 0

D. IsPalindrome method parameters are wrong

Solution

1. Step 1: Check substring length calculation

   Substring(start, length) needs length = end - start + 1, but code uses end - start, missing last character.

2. Step 2: Verify other parts

   IsPalindrome parameters and RemoveAt usage are correct; base case is correct as start == s.Length.

3. Final Answer:

   Substring length calculation is incorrect -> Option B

4. Quick Check:

   Substring length = end - start + 1 [OK]

Hint: Substring length must include end index +1 [OK]

Common Mistakes:

• Using substring length as end - start instead of end - start + 1
• Removing wrong index from current list
• Incorrect base case condition

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. 10

B. 6

C. 8

D. 4

Solution

1. Step 1: List all palindrome partitions of "racecar"

   Partitions include ["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"], and others.

2. Step 2: Count all valid palindrome partitions

   Counting carefully, there are 10 valid palindrome partitions in total.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Palindrome partitions of "racecar" = 10 [OK]

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

Common Mistakes:

• Counting only single character partitions
• Missing longer palindrome substrings like "cec" or "aceca"
• Assuming only 1 or 2 partitions