Word Break II

Problem

Return all ways to segment a string into space-separated dictionary words.

Example

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

Constraints

• 1 ≤ |s| ≤ 300

Approach

Backtracking with memoization to avoid exponential blowup.