**Solution**

**Palindrome Partitioning** https://leetcode.com/problems/palindrome-partitioning/

**Algorithm**

- Standard backtracking solution.
- Notice how the cache for is_palindrome is prepared in a DP fashion from lengths of 1,2,3,4..substrings.
- Iterate from index k to len(s)-1 (say index i) and when we find a left palindrome indicated by cache[k,i], we add the left palindrome to so_far array and recursively call for i+1.
- Terminating condition is k == len(s).

```
class Solution(object):
def is_palindrome(self, s):
N = len(s)
cache = [[False]*N for _ in range(N)]
for i in range(N):
cache[i][i] = True
if i+1 < N:
cache[i][i+1] = (s[i] == s[i+1])
for length in range(3,len(s)+1):
j = length-1
for i in range(N):
if i+j < N:
cache[i][i+j] = cache[i+1][i+j-1] and (s[i] == s[i+j])
return cache
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
result = []
self.helper(0, s, self.is_palindrome(s), [], result)
return result
def helper(self, k, s, cache, so_far, result):
if k == len(s):
result.append([x for x in so_far])
else:
for i in range(k, len(s)):
if cache[k][i]:
so_far.append(s[k:i+1])
self.helper(i+1, s, cache, so_far, result)
so_far.pop()
return
```