[LeetCode] #140 Word Break II

Recursion, time complexity: O(2^n),  Time Limit Exceeded

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(s, wordDict, result, new ArrayList<String>(), 0);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i))) {
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i);
                path.remove(path.size() - 1);
            }
        }
    }
}

Recursion + pruning(avoid repeated calculation)

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        boolean[] possible = new boolean[s.length() + 1];
        boolean[] initialized = new boolean[s.length() + 1];
        Arrays.fill(possible, false);
        Arrays.fill(initialized, false);
        helper(s, wordDict, result, new ArrayList<String>(), 0, possible, initialized);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start, boolean[] possible, boolean[] initialized) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i)) && (!initialized[i] || possible[i])) {
                int resultN = result.size();
                initialized[i] = true;
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i, possible, initialized);
                path.remove(path.size() - 1);
                possible[i] = resultN < result.size();
            }
        }
    }
}