private ArrayList<String> searchWordBreak(String s, Set<String> dict,
                Map<String, ArrayList<String>> solutions) {
            ArrayList<String> solution = solutions.get(s);
            if (solution != null) {
                return solution;
            }
            solution = new ArrayList<String>();
            for (int i = 1; i < s.length(); i++) {
                String prefix = s.substring(0, i);
                if (dict.contains(prefix)) {
                    for (String subfix : searchWordBreak(s.substring(i), dict,
                            solutions)) {
                        solution.add(prefix + " " + subfix);
                    }
                }
            }
            if (dict.contains(s)) {
                solution.add(s);
            }
            solutions.put(s, solution);
            return solution;
        }