Given a string s , partition it so that every piece is a palindrome, and return all such partitions. The list of partitions may be in any order ; within a partition the pieces stay in left-to-right order. Input format Input is [s] , e.g. [ aab ] .