public List<String> wordBreak(String s,Set<String> dict){
  List<String> words=new ArrayList<String>();
  int len=s.length();
  for (int i=1; i <= len; i++) {
    String pref=s.substring(0,i);
    if (dict.contains(pref)) {
      if (i == len) {
        words.add(pref);
      }
 else {
        String remain=s.substring(i,len);
        List<String> remainDecomp=res.containsKey(remain) ? res.get(remain) : wordBreak(remain,dict);
        if (remainDecomp != null) {
          for (          String w : remainDecomp) {
            words.add(pref + " " + w);
          }
          res.put(remain,remainDecomp);
        }
      }
    }
  }
  return words;
}

public List < String > wordBreak ( String s , Set < String > dict ) { List < String > words = new ArrayList < String > ( ) ; int len = s . length ( ) ; for ( int i = 1 ; i <= len ; i ++ ) { String pref = s . substring ( 0 , i ) ; if ( dict . contains ( pref ) ) { if ( i == len ) { words . add ( pref ) ; } else { String remain = s . substring ( i , len ) ; List < String > remainDecomp = res . containsKey ( remain ) ? res . get ( remain ) : wordBreak ( remain , dict ) ; if ( remainDecomp != null ) { for ( String w : remainDecomp ) { words . add ( pref + " " + w ) ; } res . put ( remain , remainDecomp ) ; } } } } return words ; }
dp , backtracking store successful decomposition in a map get prefix if not in dictionary , just ignore if in dictionary , check current position if reaches the end , add prefix to a solution if within length do the following : check whether the rest of the string is already decomposed if not , backtracking the rest of the string if yes , get the result from memory function if there is an result , add each word to current solution with front in
