Given a string s and a dictionary, return all possible sentences where s is segmented into dictionary words.
With s = "catsanddog" and wordDict = ["cat","cats","and","sand","dog"]:
- "cats and dog": "cats" + "and" + "dog".
- "cat sand dog": "cat" + "sand" + "dog".
- Both are valid. Return ["cats and dog", "cat sand dog"].
With s = "pineapplepenapple" and wordDict = ["apple","pen","applepen","pine","pineapple"]:
- "pine apple pen apple"
- "pineapple pen apple"
- "pine applepen apple"
Constraints: s.length . wordDict.length .