leetcode: Word Break II

Instead of returning true or false, word break II asks to record all possible breakings.

By modifying word break I, it is not hard to get the solution. The major differences are:

1. Don't return when finding a possible solution. Keep trying other cases.
2. A boolean variable to record whether a breaking point is possible or not;

Code:

public class Solution {
 public ArrayList wordBreak(String s, Set dict) {
  Set impossible = new HashSet();
  ArrayList res = new ArrayList();

  recursion(s, dict, 0, impossible, res, "");
  return res;

 }

 public boolean recursion(String s, Set dict, int current,
   Set impossible, ArrayList res, String breaks) {
  if (current == s.length()) {
   res.add(breaks.substring(0, breaks.length() - 1));
   return true;
  }

  boolean possible = false;
  for (int i = current + 1; i <= s.length(); i++) {
   if (impossible.contains(i))
    continue;
   if (dict.contains(s.substring(current, i))) {
    String newBreaks = new String(breaks);
    newBreaks = newBreaks + s.substring(current, i) + " ";
    if (recursion(s, dict, i, impossible, res, newBreaks)) {
     possible = true;
    }
   }
  }
  if (!possible) {
   impossible.add(current);
   return false;
  } else
   return true;
 }

}