Hi shenhualonga, I think memorization is theoretically helpful. For example, given a string "bba", there are two ways of reaching a, either by "b|b|a" or by "bb|a". If we use memorization, the palindrome checking for "a" can be shared.

But on the other hand, the complexity is O(n * 2 ^ (n-1)), since there are 2 ^ (n-1) ways of dividing up the string and the palindrome checking for each string is O(n) time altogether. Therefore palindrome checking is not critical, since the problem is exponential anyway. You need to generate that many strings anyway.