Palindrome Partitioning

Medium

Given a string s, partition it so that every substring of the partition is a palindrome. Return all possible palindrome partitionings, in any order.

Example 1

Input:  s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2

Input:  s = "a"
Output: [["a"]]

Constraints

• 1 <= s.length <= 16
• s contains only lowercase English letters.