classSolution:

defpartition(self,s:str) -> List[List[str]]:

n=len(s)

N=len(s)

defisPal(i,j):

if i< j:

returnis_Pal[i, j]

returnjin Pal[i]

for iinrange(n-2,-1,-1):

for jinrange(i+1, n):

is_Pal[i, j]= s[i]== s[j]and isPal(i+1, j-1)

for jinrange(N):

for iinrange(j+1):

if s[i]== s[j]and isPal(i+1, j-1):

Pal[i].add(j)

result= []

defbacktrack(left=-1,right=-1,route=[]):

ifnot isPal(left, right):

if right== n-1:

result.append(route.copy())

defbacktrack(first=0,route=[]):

if first== N:

result.append(route[:])

left= right+1

for iinrange(left, n):

route.append(s[left:i+1])

backtrack(left, i, route)

for iin Pal[first]:

route.append(s[first:i+1])

backtrack(i+1)

route.pop()