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

    private List<String> helper(String s, Set<String> dict, HashMap<String, List<String>> map){
        List<String> res = new ArrayList<>();
        if(s == null || s.length() < 1){
            return res;
        }
        if(map.containsKey(s)){
            return map.get(s);
        }
        if(dict.contains(s)){
            res.add(s);
        }
        for(int i = s.length() - 1; i >= 1; i--){
            String rightPart = s.substring(i);
            if(dict.contains(rightPart)){
                List<String> tmp = helper(s.substring(0, i), dict, map);
                if(tmp.size() > 0){
                    for(int j = 0; j < tmp.size(); j++){
                        res.add(tmp.get(j) + " " + rightPart);
                    }
                }
            }
        }
        map.put(s, res);
        return res;
    }

}