Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution 1
A straightforward way is to get all solutions by backtracking the DP table. As follows: 

However, it cannot pass the large cases.

Got another way to solve this by mingling DP and Backtrack. Slight changes to the above code will pass all test cases.