Given a string `s`, partition it so that every substring of the partition is a **palindrome**. Return all possible palindrome partitionings.
Partitions are listed in the order produced by exploring shorter leading cuts first.
Example 1
Input:s = "aab"
Output:[["a","a","b"],["aa","b"]]
Explanation:Two valid palindrome partitions.
Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters