public class Solution {

public List<String> wordBreak(String s, Set<String> dict) {

List<String> result = new ArrayList<String>();

for(int j = s.length() - 1; j >= 0; j--){

if(dict.contains(s.substring(j)))

break;

else{

if(j == 0)

return result;

}

}

for(int i = 0; i < s.length()-1; i++)

{

if(dict.contains(s.substring(0,i+1)))

{

List<String> strs = wordBreak(s.substring(i+1,s.length()),dict);

if(strs.size() != 0)

for(Iterator<String> it = strs.iterator();it.hasNext();)

{

result.add(s.substring(0,i+1)+" "+it.next());

}

}

}

if(dict.contains(s)) result.add(s);

return result;

}

}