140. Word Break II

Practice Word Break II for free on NudgeCode: Hard, Backtracking pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Add spaces to s so that every piece is a word from wordDict, and return every sentence you can build this way. A word may be used any number of times. Return [] if there is none. The sentences can be in any order.

Example

s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
->  ["cats and dog","cat sand dog"]

Constraints

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• All strings are lowercase English letters; words in wordDict are distinct