Word Break II

Given a string s and a list of words, return all possible sentences where each word in the sentence is in the list and the sentence forms s by concatenating them.

Examples
Input: ["catsanddog",["cat","cats","and","sand","dog"]]
Output: ["cat sand dog","cats and dog"]
Hints

Word Break II

Given a string s and a list of words, return all possible sentences where each word in the sentence is in the list and the sentence forms s by concatenating them.