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 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 every spot, and if a piece isn't a mirror, you undo the cut and try a different spot.

s = "a b a c"
Indices: 0 1 2 3
Partitions: [a] [b] [a] [c]
Pointers: start ↑ end ->
We try cuts between letters to form palindrome pieces.

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 piece to explore 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 with palindrome pieces

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

["a", "a", "b"] complete partition

Why: Reached end with all palindrome pieces, record this partition

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

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

Why: Discard invalid palindrome piece and try other options

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 piece from start

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

["aa", "b"] complete partition

Why: Reached end with all palindrome pieces, record this partition

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// Check if substring s[left..right] is palindrome
bool isPalindrome(char *s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

// Structure to hold one partition
typedef struct {
    char **parts;
    int size;
    int capacity;
} Partition;

// Initialize Partition
void initPartition(Partition *p) {
    p->capacity = 10;
    p->size = 0;
    p->parts = malloc(sizeof(char*) * p->capacity);
}

// Add part to Partition
void addPart(Partition *p, char *part) {
    if (p->size == p->capacity) {
        p->capacity *= 2;
        p->parts = realloc(p->parts, sizeof(char*) * p->capacity);
    }
    p->parts[p->size++] = strdup(part);
}

// Remove last part from Partition
void removeLastPart(Partition *p) {
    if (p->size > 0) {
        free(p->parts[p->size - 1]);
        p->size--;
    }
}

// Print one partition
void printPartition(Partition *p) {
    for (int i = 0; i < p->size; i++) {
        printf("%s", p->parts[i]);
        if (i != p->size - 1) printf(", ");
    }
    printf("\n");
}

// Backtracking function to find palindrome partitions
void backtrack(char *s, int start, Partition *current) {
    int n = strlen(s);
    if (start == n) {
        printPartition(current); // print one valid partition
        return;
    }
    for (int end = start; end < n; end++) {
        if (isPalindrome(s, start, end)) {
            int len = end - start + 1;
            char *substr = malloc(len + 1);
            strncpy(substr, s + start, len);
            substr[len] = '\0';
            addPart(current, substr); // add palindrome part
            free(substr);
            backtrack(s, end + 1, current); // recurse for remaining string
            removeLastPart(current); // backtrack
        }
    }
}

int main() {
    char s[] = "aab";
    Partition current;
    initPartition(&current);
    backtrack(s, 0, &current);
    // Free allocated memory
    for (int i = 0; i < current.size; i++) {
        free(current.parts[i]);
    }
    free(current.parts);
    return 0;
}

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

Check if current substring is palindrome to decide if we can partition here

addPart(current, substr); // add palindrome part

Add the palindrome substring to current partition list

backtrack(s, end + 1, current); // recurse for remaining string

Recurse to partition the rest of the string after current palindrome

removeLastPart(current); // backtrack

Remove last added part to try other partitions (undo choice)

Output

a, a, b

aa, b

Complexity Analysis

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

Space: O(n) for recursion stack and current partition storage

vs Alternative: Compared to brute force without palindrome checks, this prunes invalid partitions early but still exponential in worst case

Edge Cases

empty string

prints nothing as there are no partitions

DSA C

if (start == n) { printPartition(current); return; }

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

finds all partitions like ["a", "a", "a"], ["aa", "a"], ["a", "aa"], ["aaa"]

DSA C

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

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

only partitions with single characters are found

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 all cuts and check palindrome validity to prune invalid paths.

Common Mistakes

Mistake: Not backtracking properly by forgetting to remove last added part after recursion
Fix: Always remove last part after recursive call to explore other partitions

Mistake: Checking palindrome inefficiently multiple times for same substrings
Fix: Use a helper function to check palindrome once per substring or memoize results

Summary

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

Use it when you need to list all palindrome partitions of a string.

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