Given a string input_str, return all possible ways to partition input_str into non-empty substrings such that each substring is a palindrome. Each partition should be represented as a list of strings. Return a list of all such partitions.
Example 1
Input: racecar
Output: [[r, a, c, e, c, a, r], [r, a, cec, a, r], [r, aceca, r], [racecar]]
Explanation: All possible partitions where each substring is a palindrome.
Example 2
Input: noon
Output: [[n, o, o, n], [n, oo, n], [noon]]
Explanation: All possible partitions where each substring is a palindrome.
Constraints
Case 1
Input: 'abcba'
Expected: [['a', 'b', 'c', 'b', 'a'], ['a', 'bcb', 'a'], ['abcba']]
Case 2
Input: 'madam'
Expected: [['m', 'a', 'd', 'a', 'm'], ['m', 'ada', 'm'], ['madam']]
Case 3
Input: 'deed'
Expected: [['d', 'e', 'e', 'd'], ['d', 'ee', 'd'], ['deed']]
Case 4
Input: 'level'
Expected: [['l', 'e', 'v', 'e', 'l'], ['l', 'eve', 'l'], ['level']]