public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        int n = s.length();
        List<String>[] F = (List<String>[]) new ArrayList[n+1];
        Arrays.fill(F, new ArrayList<String>());
        F[n].add("");
        
        for (int i = n - 1; i >= 0; i--) {
            for (int k = i; k <= n - 1; k++) {
                String sub = s.substring(i, k+1);
                if (dict.contains(sub) && !F[k+1].isEmpty()) {
                    if (k == n-1) {
                        F[i].add(sub);
                    }
                    else {
                        for (int j = 0; j < F[k+1].size(); j++) {
                            F[i].add(sub + " " + F[k+1].get(j));
                        }
                    }
                }
            }
        }
        
        return F[0];
    }
}

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        int n = s.length();
        List<Integer>[] F = (List<Integer>[]) new ArrayList[n+1];
        F[n] = new ArrayList<Integer>();
        
        for (int i = n - 1; i >= 0; i--) {
            for (int k = i; k <= n - 1; k++) {
                String sub = s.substring(i, k+1);
                if (dict.contains(sub) && F[k+1] != null) {
                    if (F[i] == null)
                        F[i] = new ArrayList<Integer>();
                    F[i].add(k);
                }
            }
        }
        List<String> sol = new ArrayList<>();
        if (F[0] == null) return sol;
        
        String parSol = "";
        recConstruct(s, F, 0, parSol, sol);
        return sol;
    }
    
    private void recConstruct(String s, List<Integer>[] F, int i, String parSol, List<String> sol) {
        if (i == s.length()) {
            sol.add(parSol);
            return;
        }
        
        for (Integer k : F[i]) {
            if (parSol.length() == 0)
                recConstruct(s, F, k+1, s.substring(i, k+1), sol);
            else
                recConstruct(s, F, k+1, parSol+" "+s.substring(i, k+1), sol);
        }
        
    }
}