public boolean wordBreak2(String s, Set<String> dict) {
        if(s.length() == 0) return true;
        for(int i = 1; i <= s.length(); i++){
            String sub = s.substring(0, i);
            if(dict.contains(sub) && wordBreak2(s.substring(i), dict)) return true;
        }
        return false;
    }