Problem URL: Palindrome partitioning

We will solve it through backtracking. We will check every possible substring, if it is palindrome, then we add it to the partition, when we are at the end of the string, we add it to the result. We will run it for every possible solution, and then return the result.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res, part = [], []

        def dfs(i):
            if i >= len(s):
                res.append(part.copy())
                return
            for j in range(i, len(s)):
                if self.isPalindrome(s, i, j):
                    part.append(s[i:j+1])
                    dfs(j+1)
                    part.pop()

        dfs(0)
        return res

    def isPalindrome(self, s: str, l: int, r: int) -> bool:
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l+1, r-1
        return True

Time Complexity: O(2^n)
Space Complexity: O(2^n)