Below is my solution. The detail view tells me it's within the fastest in python. It is really easy to understand. I basically go through an existing partition, index by index, and each time I find a new palindrome, I branch out with the new partition and go on. It's of course a recursive solution (Depth-First). Comments are in the code.
def partitionRec(p, index, ps): # If we're at the last position of the current partition, add the partition and leave. if index == len(p)-1: ps += [p] return # Tries to create a palindrome at "index" if p[index] == p[index+1]: # first way 'ab', 'ba' pi = p[:] pi[index] = pi[index] + pi[index+1] del pi[index+1] partitionRec(pi, index, ps) #go look for other partitions based on the new one if index > 0 and p[index-1]==p[index+1]: # second way 'ab', 'c', 'ba' pii = p[:] pii[index-1] = pii[index-1] + pii[index] + pii[index+1] del pii[index+1] del pii[index] partitionRec(pii, index - 1, ps) #go look for other partitions based on the new one # Go forward on the ame partition partitionRec(p, index+1, ps) def partition(s): p = [c for c in s] #initialize the first partition ps =  #initialize list of partitions partitionRec(p,0,ps) #go! return ps class Solution: # @param s, a string # @return a list of lists of string def partition(self, s): return partition(s)
The only tricky part is to understand why we have all the palindrome partitions this way, even while not going back when we have a new partition. It comes from the properties of a palindrome, which can always be grown from its middle (second case in the code) or left to right.