class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, wordDict, 0, new LinkedList<String>(), new HashSet<>());
    }

    public List<String> wordBreak(String s, List<String> wordDict, int offset, LinkedList<String> history, HashSet<Integer> deadEnds) {
        if (offset == s.length()) {
            List<String> result = new LinkedList<>();
            result.add(String.join(" ", history));
            return result;
        }

        List<String> possibleCombinations = new LinkedList<>();

        if (deadEnds.contains(offset))
            return possibleCombinations;

        for(String w : wordDict) {
            if (!s.startsWith(w, offset))
                continue;
            history.addLast(w);
            possibleCombinations.addAll(wordBreak(s, wordDict, offset + w.length(), history, deadEnds));
            history.removeLast();
        }

        if (possibleCombinations.size() == 0)
            deadEnds.add(offset);
        return possibleCombinations;
    }
}