Given a string input_string, generate all possible ways to partition input_string such that every substring in each partition is a palindrome. Return a list of lists, where each inner list represents a valid partition of input_string into palindromic substrings.
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 of racecar into palindromic substrings.
Example 2
Input: "noon"
Output: [[n, o, o, n], [n, oo, n], [noon]]
Explanation: All possible partitions of noon into palindromic substrings.
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: "level"
Expected: [['l', 'e', 'v', 'e', 'l'], ['l', 'eve', 'l'], ['level']]