Palindrome Partitioning Using Backtracking in DSA C - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: Imagine you have a word, and you want to split it into parts where each part reads the same forwards and backwards. This is called palindrome partitioning. For example, the word "noon" can be split as "n" | "oo" | "n" where each part is a palindrome.

🎯 Goal: You will write a program in C that finds all possible ways to split a given word into palindrome parts using backtracking. You will build the solution step-by-step, starting from checking palindromes, then setting up backtracking, and finally printing all partitions.

📋 What You'll Learn

Create a function to check if a substring is a palindrome

Use backtracking to find all palindrome partitions

Store partitions dynamically using arrays

Print all palindrome partitions clearly

💡 Why This Matters

🌍 Real World

Palindrome partitioning is useful in text processing, DNA sequence analysis, and data compression where symmetrical patterns matter.

💼 Career

Understanding backtracking and string manipulation is important for software engineers working on algorithms, coding interviews, and complex problem solving.

1

Create a function to check palindrome

Write a function called isPalindrome that takes a char* string, a start index, and an end index, and returns 1 if the substring from start to end is a palindrome, otherwise 0. Use a while loop to compare characters from both ends.

DSA C

#include 
#include 

// Write isPalindrome function here

int main() {
    return 0;
}

Hint

Compare characters from the start and end indexes moving towards the center. If any pair differs, return 0. If all match, return 1.

2

Set up backtracking function

Create a function called backtrack that takes char* str, int start, a 2D array result to store partitions, an int* resultSize, a temporary array temp to hold current partition strings, and an int tempSize. This function will explore all palindrome partitions starting from start index.

DSA C

#include 
#include 

int isPalindrome(char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

// Write backtrack function here

int main() {
    return 0;
}

Hint

Use a loop from start to end of string. If substring is palindrome, add it to temp and call backtrack recursively from next index.

3

Initialize variables and call backtracking

In main, create a string str with value "aab". Declare a 2D array result to store partitions, an int resultSize initialized to 0, and a temporary 2D array temp. Call backtrack with these variables starting from index 0.

DSA C

#include 
#include 

int isPalindrome(char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

void backtrack(char* str, int start, char result[100][100], int* resultSize, char temp[100][100], int tempSize) {
    int len = strlen(str);
    if (start == len) {
        for (int i = 0; i < tempSize; i++) {
            strcpy(result[*resultSize] + i * 100, temp[i]);
        }
        (*resultSize)++;
        return;
    }
    for (int end = start; end < len; end++) {
        if (isPalindrome(str, start, end)) {
            int subLen = end - start + 1;
            strncpy(temp[tempSize], str + start, subLen);
            temp[tempSize][subLen] = '\0';
            backtrack(str, end + 1, result, resultSize, temp, tempSize + 1);
        }
    }
}

int main() {
    char str[] = "aab";
    char result[100][100] = {0};
    int resultSize = 0;
    char temp[100][100] = {0};
    // Call backtrack here
    return 0;
}

Hint

Initialize the string and arrays, then call backtrack starting from index 0.

4

Print all palindrome partitions

After calling backtrack in main, write a for loop to print all palindrome partitions stored in result. Each partition is stored as concatenated strings of length 100. Print each partition on a new line with parts separated by spaces.

DSA C

#include 
#include 

int isPalindrome(char* str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return 0;
        }
        start++;
        end--;
    }
    return 1;
}

void backtrack(char* str, int start, char result[100][100], int* resultSize, char temp[100][100], int tempSize) {
    int len = strlen(str);
    if (start == len) {
        for (int i = 0; i < tempSize; i++) {
            strcpy(result[*resultSize] + i * 100, temp[i]);
        }
        (*resultSize)++;
        return;
    }
    for (int end = start; end < len; end++) {
        if (isPalindrome(str, start, end)) {
            int subLen = end - start + 1;
            strncpy(temp[tempSize], str + start, subLen);
            temp[tempSize][subLen] = '\0';
            backtrack(str, end + 1, result, resultSize, temp, tempSize + 1);
        }
    }
}

int main() {
    char str[] = "aab";
    char result[100][100] = {0};
    int resultSize = 0;
    char temp[100][100] = {0};
    backtrack(str, 0, result, &resultSize, temp, 0);
    for (int i = 0; i < resultSize; i++) {
        // Print each partition
    }
    return 0;
}

Hint

Loop through all stored partitions and print each substring separated by spaces on a new line.