LeetCode 140 Word Break II - Problem Statement

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: $1 \le$ s.length $\le 20$. $1 \le$ wordDict.length $\le 1000$.