Recursion Backtracking Combinatorics
Proficient Level

Implement the palindromePartitionCount method that counts palindrome partitions possible for the text.

The input is a string text.

Your task is to count how many ways the string can be split into non-empty substrings so that every substring is a palindrome.

For example, aab has two valid palindrome partitions: a | a | b and aa | b. Therefore, the answer is 2.

Example 1
Input:
text (string) = aab
Return:
(int) 2
Example 2
Input:
text (string) = a
Return:
(int) 1
Example 3
Input:
text (string) = aaa
Return:
(int) 4

Use backtracking to try every possible cut position.

Starting from the current index, take each possible substring ending at or after that index. If the substring is a palindrome, continue partitioning the remaining part of the string.

When the current index reaches the end of the string, one complete palindrome partition has been formed, so increase the count.

Pseudocode:

function palindromePartitionCount(text):
    count = 0
    backtrack(start):
        if start == length of text:
            count++
            return
        for end from start to length of text - 1:
            if isPalindrome(text, start, end):
                backtrack(end + 1)
    backtrack(0)
    return count
function isPalindrome(text, left, right):
    while left < right:
        if text[left] != text[right]:
            return false
        left++
        right--
    return true
Run your code to see the result.