public static ArrayList<String> wordBreak(String s, Set<String> dict){
        if(s == null || dict == null){
            return new ArrayList<String>();
        }
        if(s.length() == 0 || dict.size() == 0){
            return new ArrayList<String>();
        }

        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> subRes = new ArrayList<String>();

        //use dp to determine if s[0,n-1] can be represented by dict (exactly the same as wordbreak1)
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i < s.length()+1; i++){
            for(int j = 0; j < i; j++){
                //if s[0,j-1] can be represented by dict and s[j,i-1] is in dict, set dp[i] to true
                if(dp[j] == true && dict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        //if s[0,n-1] can not be represented by dict
        if(dp[s.length()] == false){
            return res;
        }

        dfs(0, s, dict, res, subRes, dp);
        return res;
    }