Problem

Given a non-empty string s and a dictionary containing a list of non-empty words wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Examples

Example 1:

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: ["cats and dog", "cat sand dog"]

Example 2:

s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]

Constraints

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• The input string s is guaranteed to be non-empty.