class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        return wordBreak_helper(s, wordDict, 0);

    }

    public boolean wordBreak_helper(String s, List<String> wordDict, int i_dict) {
        if (i_dict == wordDict.size()) {
            if (s.isEmpty()) return true;
            return false;
        }

        // use it
        String word = wordDict.get(i_dict);
        boolean result_use_it = wordBreak_helper(s.replaceAll(word,""), wordDict, i_dict + 1);
        // not use it
        boolean result_not_use_it = wordBreak_helper(s, wordDict, i_dict + 1);

        return result_use_it || result_not_use_it;

    }
}