Word Break II

Problem Given a string s and a dictionary of words, return all possible ways to segment s into a space-separated sequence of dictionary words. Each returned string is a valid full segmentation of s.

Input / Output

• Input: string s, list of dictionary words.
• Output: all sentences that are valid segmentations of s (any order).

Constraints

• 1 ≤ |s| ≤ 300.
• The same dictionary word may be reused across a segmentation.

Example

• s = "catsanddog", dict = [cat,cats,and,sand,dog] → ["cats and dog","cat sand dog"].