import java.util.*;

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashMap<String, List<String>> map = new HashMap<>();
        return dfs(s, wordDict, map);
    }

    private List<String> dfs(String s, List<String> wordDict, HashMap<String, List<String>> map) {
        List<String> res;
        if ((res = map.get(s)) != null) return res;
        res = new ArrayList<>();
        if (s.equals("")) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> list = dfs(s.substring(word.length()), wordDict, map);
                for (String suffix : list) {
                    if (suffix.equals("")) res.add(word);
                    else res.add(word + " " + suffix);
                }
            }
        }
        map.put(s, res);
        return res;
    }
}