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.

Cheers!