```
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
if len(s) == 0:
return [[]]
if len(s) ==1:
return [[s]]
results = []
#find all candidates of palindromes starting with the 1st letter.
candidates = self.generate(s)
#concatenating each candidate with the following results
for item in candidates:
nxt_res = self.partition(s[len(item):])
for nxt_item in nxt_res:
if nxt_item:
results.append([item] + nxt_item )
else:
results.append([item])
return results
#generate all the candidates of palindrome starting with the first letter
def generate(self, s):
candidates = []
for i in xrange(len(s)):
if s[i] == s[0]:
if self.check(s[0:i+1]):
candidates.append(s[0:i+1])
return candidates
#check if a string is palindrome
def check(self,s):
'''We can also use return s==s[::-1]'''
if len(s) == 0:
return False
first = 0
last = len(s)-1
while first <= last:
if s[first] != s[last]:
return False
first += 1
last -= 1
return True
```

The idea is to find all palindrome strings starting with the first letter, then find partitions of the rest of string except for the palindrome substrings. Therefore, it's a combination of recursion and BFS.