653. Expression Add Operators

Code(Language:C++) (Judger:cloudjudge-cluster-5)

class Solution {
public:
    /**
     * @param num: a string contains only digits 0-9
     * @param target: An integer
     * @return: return all possibilities
     */
    vector<string> addOperators(string &num, int target) {
        // write your code here
        // DFS，recursion的body 更复杂些。
        vector<string> res; 
        dfs(num, target, res, "", 0, 0, 0); 
        return res; 
    }
    void dfs(string &num, int target, vector<string> &res, string resElem, int start, int sum, int diff){
         //DFS body的关键是以什么规则，拆成子问题。
        //首先要看的是：在当前看，有哪些情况case。先解决当前的所有case。
        //然后，每个当前case下都有子问题。
        if(start == num.size()){
            if(sum == target){
                res.push_back(resElem); 
            }
            return; 
        }
        for(int i = start; i < num.size(); i++){
            if(num[start] == '0'){
                if(resElem.size() == 0){
                    //只有一种情况
                    dfs(num, target, res, resElem + "0", i + 1, 0, 0); 
                }
                else{
                    //当前三种情况，形成了三个子问题
                    dfs(num, target, res, resElem + "+0", i + 1, sum, 0); //子问题 
                    dfs(num, target, res, resElem + "-0", i + 1, sum, 0); //
                    dfs(num, target, res, resElem + "*0", i + 1, sum - diff + diff * 0, 0); 
                }
                break; 
            }
            else{
                string sub = num.substr(start, i - start + 1); 
                long long n = stoll(sub); 
                if(resElem.size() == 0){
                    dfs(num, target, res, resElem + sub, i + 1, n, n); 
                    
                }
                else{
                    dfs(num, target, res, resElem + "+" + sub, i + 1, sum + n, n); 
                    dfs(num, target, res, resElem + "-" + sub, i + 1, sum - n, -n); 
                    dfs(num, target, res, resElem + "*" + sub, i + 1, sum - diff + n * diff,  n * diff); 
                }
            }
        }
        return; 
    }
};