Two methods dfs backtracking and dfs backtracking with dp

    1. class Solution:
    2.     def partition(self, s: str) -> List[List[str]]:
    3.         #backtracking
    4.         def dfs(start, s, curr, result):
    5.             if start >= len(s):
    6.                 ans = [i for i in curr]
    7.                 result.append(ans)
    8.             for end in range(start, len(s)):
    9.                 if isPalindrome(s, start, end):
    10.                     curr.append(s[start:end+1])
    11.                     dfs(end+1, s, curr, result)
    12.                     curr.pop() 
    14.         def isPalindrome(s, start, end):
    15.             while start <= end and s[start] == s[end]:
    16.                 start += 1
    17.                 end -= 1
    18.             if end - start <= 0:
    19.                 return True
    20.             else:
    21.                 return False
    23.         if not s:
    24.             return []
    25.         result = []
    26.         dfs(0, s, [], result)
    28.         return result