Every Way to Read the Message

A message lost all of its spaces. Given the run-together text s and a list words of known words, write all_sentences(s, words) that returns every way to put spaces back so that each piece is one of the words. A word may be used any number of times.

Return each sentence as a string with a single space between words, and return the list sorted in Python's normal string order. Return an empty list if the text cannot be split.

Examples

all_sentences("sunflowerseeds", ["sun", "flower", "sunflower", "seed", "seeds", "flowers", "eeds"])
# returns ['sun flower seeds', 'sun flowers eeds', 'sunflower seeds']
all_sentences("notebook", ["note", "book", "notebook", "no", "tebook"])
# returns ['no tebook', 'note book', 'notebook']
all_sentences("abc", ["ab", "bc"])  # returns []

Constraints

• 1 <= len(s) <= 40
• words holds 1 to 50 different words of 1 to 10 lowercase letters.
• No answer holds more than 5,000 sentences.