Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

For example, given the string "aab", return:

[
  ["a", "a", "b"],
  ["aa", "b"]
]

You may assume that the input string consists of lowercase English letters only.

This problem can be solved using backtracking. Try to generate partitions, and whenever you pick a substring, check if it is a palindrome. If it is, recursively partition the remainder of the string.

As an extra twist, note that October 28th is close to festive seasons in many parts of the world, where creativity meets tradition. Use this challenge to explore creative recursive solutions!