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.

Practice

1. What is the main goal of palindrome partitioning using backtracking on a string s?

easy

A. To find the longest palindrome substring in s

B. To split s into all possible substrings where each substring is a palindrome

C. To count the number of palindromes in s

D. To reverse the string s using recursion

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing the string into parts where each part reads the same forwards and backwards.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome substrings.

3. Final Answer:

   To split s into all possible substrings where each substring is a palindrome -> Option B

4. Quick Check:

   Palindrome partitioning = all palindrome substrings [OK]

Hint: Backtracking explores all palindrome splits [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only counts palindromes instead of listing partitions
• Assuming it reverses the string

2. Which of the following is the correct base case condition in a backtracking function for palindrome partitioning of string s starting at index start?

easy

A. if (start == s.length()) add current partition to result and return;

B. if (start > s.length()) return false;

C. if (start == s.length()) return true;

D. if (start < 0) return;

Solution

1. Step 1: Identify when to stop recursion

   When start reaches the length of the string, it means the entire string is partitioned.

2. Step 2: What to do at base case

   At this point, add the current list of palindrome substrings to the result list and return to explore other partitions.

3. Final Answer:

   if (start == s.length()) add current partition to result and return; -> Option A

4. Quick Check:

   Base case adds partition when start reaches string end [OK]

Hint: Add partition when start equals string length [OK]

Common Mistakes:

• Returning true/false instead of adding partition
• Checking start > length instead of == length
• Using invalid index checks like start < 0

3. What will be the output partitions for the string "aab" using palindrome partitioning with backtracking?

medium

A. [["aab"]]

B. [["aa", "ab"]]

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

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

Solution

1. Step 1: Check all palindrome substrings

   "a" is palindrome, "aa" is palindrome, "b" is palindrome, but "ab" and "aab" are not.

2. Step 2: List all palindrome partitions

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Check substrings palindrome before partitioning [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the partition ["aa", "b"]
• Returning the whole string as one partition

4. Given the following code snippet for palindrome partitioning, what is the error?

void backtrack(char* s, int start, char** current, int currentSize, char*** result, int* returnSize) {
  if (start == strlen(s)) {
    result[*returnSize] = current;
    (*returnSize)++;
    return;
  }
  for (int end = start; end < strlen(s); end++) {
    if (isPalindrome(s, start, end)) {
      current[currentSize] = substring(s, start, end);
      backtrack(s, end + 1, current, currentSize + 1, result, returnSize);
    }
  }
}

medium

A. Assigning current directly to result causes shared reference issues

B. The base case condition is incorrect

C. The loop should run from end = 0 to end < strlen(s)

D. Missing return statement after recursive call

Solution

1. Step 1: Analyze base case assignment

   Assigning current pointer directly to result[*returnSize] stores the same reference for all partitions.

2. Step 2: Understand backtracking data handling

   We must copy the current partition array to avoid overwriting when backtracking continues.

3. Final Answer:

   Assigning current directly to result causes shared reference issues -> Option A

4. Quick Check:

   Copy partitions to result to avoid shared references [OK]

Hint: Copy current partition before adding to result [OK]

Common Mistakes:

• Not copying current partition array
• Incorrect loop range for end index
• Ignoring base case correctness

5. How can you optimize palindrome checking in backtracking palindrome partitioning for string s of length n?

hard

A. Skip palindrome checking and add all substrings to partitions

B. Check palindrome by reversing substring every time during recursion

C. Precompute a 2D boolean table dp where dp[i][j] is true if substring s[i..j] is palindrome

D. Use a hash map to store all substrings and their palindrome status

Solution

1. Step 1: Understand palindrome checking cost

   Checking palindrome by reversing substring each time costs O(n) per check, leading to O(n^3) overall.

2. Step 2: Use dynamic programming optimization

   Precompute a 2D table dp where dp[i][j] stores palindrome status for substring s[i..j]. This reduces palindrome checks to O(1).

3. Step 3: Benefit in backtracking

   Using dp speeds up backtracking by avoiding repeated palindrome checks.

4. Final Answer:

   Precompute a 2D boolean table dp where dp[i][j] is true if substring s[i..j] is palindrome -> Option C

5. Quick Check:

   DP table for palindrome checking optimizes backtracking [OK]

Hint: Use DP table to check palindrome in O(1) time [OK]

Common Mistakes:

• Reversing substring every time causing slow performance
• Using hash map adds unnecessary overhead
• Skipping palindrome checks leads to wrong partitions