# Given a string s, partition substrings in the string s
# such that every substring in it is a palindrome. Return
# all possible palindrome partitions of s.

def is_palindrome(s, start, end):
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

def dfs(s, result, path, start):
    if start >= len(s):
        result.append(list(path))
    for end in range(start, len(s)):
        if is_palindrome(s, start, end):
            path.append(s[start:end + 1])
            dfs(s, result, path, end + 1)
            path.pop()

def partition(s):
    result = []
    dfs(s, result, [], 0)
    return result

print(partition("aab"))