Palindrome Partitions

Given a string s, return all possible ways to partition s such that every substring is a palindrome. A palindrome is a string that reads the same forwards and backwards. For example, for the string aab, the valid partitions are ["a", "a", "b"] and ["aa", "b"].

Formally, if the input string is \(s = s_0s_1\ldots s_{n-1}\), then each partition is a sequence of substrings where every substring \(s_i \ldots s_j\) satisfies \(s_i \ldots s_j = (s_i \ldots s_j)^R\). The order of the partitions should follow a standard backtracking approach.

inputFormat

The input is given via standard input (stdin) as a single line containing a non-empty string s consisting of lowercase letters.

outputFormat

Output the list of all possible palindrome partitionings of s in JSON format. The output should be printed to standard output (stdout) and must exactly match the JSON format produced by JSON.stringify in languages that support it.

a

[["a"]]