Word Break II (all possible sentences)?

List<string> WordBreak(string s, IList<string> wordDict) {

var wordSet = new HashSet<string>(wordDict);

var memo = new Dictionary<int, List<string>>();

return DFS(0);

List<string> DFS(int start) {

if (memo.ContainsKey(start)) return memo[start];

var res = new List<string>();

if (start == s.Length) {

res.Add("");

return res;

for (int end = start + 1; end <= s.Length; end++) {

string word = s.Substring(start, end - start);

if (wordSet.Contains(word)) {

foreach (var sub in DFS(end)) {

string space = sub.Length == 0 ? "" : " ";

res.Add(word + space + sub);

memo[start] = res;

return res;

Follow on: