Word Break II
Hard · Backtracking · about 30 minutes
Asked at Amazon, Google, Meta, Microsoft, Bloomberg, Apple.
Given a string s and a dictionary wordDict, add spaces to s to build sentences in which every word is in the dictionary. Return all such sentences, in any order. Dictionary words may be reused.