ArrayList<String> wordBreakDFS( String s, Set<String> dict ) {
        ArrayList<String> result = new ArrayList<String>(), tmpList;

        for( int i = 0; i < s.length(); i++ ) {
            String head = s.substring(0, i+1);
            String tail = s.substring(i+1);
            if( dict.contains(head) ) {
                if( tail.length() == 0 ) {
                    result.add( head );
                    break;
                }
                if( cache.containsKey( tail ) ) {
                    tmpList = cache.get( tail );
                } else {
                    tmpList = wordBreakDFS( tail, dict );
                }
                for( String ss : tmpList ) {
                    result.add( head + " " + ss );
                }
            }
        }

        cache.put( s, result );

        return result;
    }