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:
dfs + word break 1 = Time Limit Exceeded, died at "aaaaaaaaaaaaaaaaaaaaaaaaa..." 
improvement: only save routes, start from the end.

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList> dp = new ArrayList>();   
        for(int i = 0; i <= s.length(); i++){
            dp.add(new ArrayList());
        }
        ArrayList ret = new ArrayList();
        for(int i = 0; i < s.length(); i++){
            if(i > 0 && dp.get(i) == null) continue; // dp.get(i).size() == 0;
            for(String tmp : dict){
                int end = i + tmp.length();
                if(end > s.length()) continue;
                String str = s.substring(i, end);
                if(str.equals(tmp)){
                    dp.get(end).add(i);
                }
            }
        }
        StringBuilder strb = new StringBuilder();
        helper(s, dp, ret, strb, s.length(), 0);
        return ret;
    }
    public void helper(String s, ArrayList> dp, ArrayList ret, StringBuilder strb, int cur, int step){
        if(cur == 0){
            ret.add(strb.toString());
            return;
        }
        
        for(int i : dp.get(cur)){
            if(step > 0) strb.insert(0, " ");
            strb.insert(0, s.substring(i, cur));
            helper(s, dp, ret, strb, i, step + 1);
            strb.delete(0, cur-i);
            if(step > 0) strb.delete(0, 1);
        }
    }
}