LeetCode #140 - Word Break II Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. ### Input/Output Examples: **Input:** s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"] **Output:** ["cats and dog", "cat sand dog"] ### Constraints: - The input string will have a length in the range [1, 20]. - The dictionary has a maximum size of 1000 and the lengths of the words in the dictionary are not more than 20 characters.