140. Word Break II

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        HashMap<String, List<String>> used = new HashMap<>();
        return helper(s, wordSet, used);
    }
    
    private List<String> helper(String s, Set<String> wordSet, HashMap<String, List<String>> used) {
        if (used.containsKey(s)) {
            return used.get(s);
        }
        if (s.length() == 0) {
            return null;
        }
        List<String> res = new ArrayList<>();

        for (int i = 1; i <= s.length(); i++) {
            String subString = s.substring(0, i);
            List<String> partRes = null;
            if (wordSet.contains(subString)) {
                partRes = helper(s.substring(i), wordSet, used);
                if (partRes == null) {
                    res.add(subString);
                } else {
                    for (String str : partRes) {
                        res.add(subString + " " + str);
                    }
                }
            }
        }
        used.put(s, res);
        return res;
    }
}