131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning

Python

Backtracking

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

        def backtracking(start: int, stack: list):
            if start == len(s):
                nonlocal ans
                ans.append(stack[:])
                return

            for end in range(start+1, len(s)+1):
                cand = s[start:end]
                if cand != cand[::-1]:
                    continue
                stack.append(cand)
                backtracking(end, stack)
                stack.pop()

        backtracking(0, [])

        return list(ans)