def partition(self, s):
res = []
self.dfs(s, [], res)
return res
def dfs(self, s, path, res):
if not s: # backtracking
res.append(path)
for i in xrange(1, len(s)+1):
if self.isPar(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)
def isPar(self, s):
return s == s[::1]
Python easy to understand backtracking solution.

Here is a revised version with comments:
def partition(self, s): res = [] self.dfs(s, [], res) return res def dfs(self, s, path, res): if not s: res.append(path[:]) # take care here return # backtracking for i in xrange(1, len(s)+1): if self.isPar(s[:i]): path.append(s[:i]) self.dfs(s[i:], path, res) path.pop() # simulate stack here def isPar(self, s): return s == s[::1]

I have some discussion in other similar issue, and I think the reason should be that if we use path during the recursive function call, it will use the reference of path, so if path is modified later, the content of res will be updated as well. Thus we will get empty list in the end.
But if we use path[:], it will create a new list and append it to res. The change of path will not affect the content of res