Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Both ["a","a","b"] and ["aa","b"] are valid partitions where every substring is a palindrome.
Example 2:
Input: s = "a"
Output: [["a"]]
Explanation: The only partition is the single character itself.
Example 3:
Input: s = "aba"
Output: [["a","b","a"],["aba"]]
Explanation: We can partition into individual palindromes ["a","b","a"] or recognize the entire string as a palindrome ["aba"].
1 <= s.length <= 16s contains only lowercase English letters