class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if not s:
            return []

        self.ans = []
        self.dfs(s, [], 0, len(s))
        return self.ans

    def dfs(self, s, partitions, start, end):
        # end of recursion
        if start >= end:
            self.ans.append(list(partitions))
            return

        # define and spliit
        for idx in range(start, end):
            split_s = s[start:idx+1] # least one word, max = [start:(end-1+1)] = [start:end]
            if self.is_palindrome(split_s):
                partitions.append(split_s)
                self.dfs(s, partitions, idx+1, end) # go next
                partitions.pop()

        return

    def is_palindrome(self, s):
        print(s)
        start = 0
        end = len(s)-1
        while(start <= end and s[start] == s[end]): 
            start += 1
            end -= 1
        else:
            if start <= end: # check
                return False
            else:
                return True