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

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

        if (s == null || s.length() == 0) {
            return ret;
        }

        int n = s.length();
        //because check the subString of String word, position 0 must be true
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            //check the length of (0-i)
            if (dict.contains(s.substring(0, i))) {
                dp[i] = true;
                continue;
            }
            //check the length of all possible combinations.
            //like (0-3) && (4-i)..
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        //like the word break, this DP used to check if the String word can be made up by words in dict.
        if (dp[n] == false) {
            //if not, return 
            return ret;
        }
        //if yes, pass the params into the helper method
        StringBuilder cur = new StringBuilder();
        helper(s, 0, cur, ret, dict);

        return ret;
    }