Solutions

# Backtracking solution: for each index, we can either split the string or not. If we split, we check if the piece is a palindrome, and if it is, we recurse on the remaining string. If we don't split, we just advance the pointer and recurse.

# O(n* 2^n) time, O(n) space (2^n subsets, and O(n) space for the recursion stack)
class Solution:
    def partition(self, s: str) -> list[list[str]]:
        res = []
        part = []

        def dfs(j: int, i: int):
            if i >= len(s):
                if i == j:
                    # Add the split only if every piece is palindrome
                    res.append(part.copy())
                return

            if self.is_palindrome(s[j : i+1]):
                # Split the string and recurse
                part.append(s[j : i+1])
                dfs(i+1, i+1)
                # Backtrack
                part.pop()

            # Don't split, just advance the i pointer
            dfs(j, i+1)
            
        dfs(0, 0)
        return res
        
    def is_palindrome(self, s: str) -> bool:
        l,r = 0, len(s)-1
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True


class Solution:
    def partition(self, s: str) -> list[list[str]]:
        res = []
        self.rec(s, [], 0, res)
        return res
    
    def rec(self, s, curr, start, res):
        if start == len(s):
            res.append(curr)
        else:
            for i in range(start, len(s)):
                if self.is_palindrome(s, start, i):
                    self.rec(s, curr + [s[start:i+1]], i+1, res )
            
    def is_palindrome(self, s, start, end):
        while start <= end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True