Very concise C++ solution


  • 6
    G
    class Solution {
    public:
        void DFS(string num, long sum, string path, int pos, long pre, int val)
        {
            pre = pre*10 + num[pos]-'0';
            if(pre > INT_MAX) return;
            if(sum+pre*val ==0 && pos== num.size()-1) result.push_back(path+num[pos]);
            if(pos== num.size()-1) return;
            if(pre) DFS(num, sum, path+num[pos], pos+1, pre, val);
            DFS(num, sum+pre*val, path+num[pos]+'+', pos+1, 0, 1);
            DFS(num, sum+pre*val, path+num[pos]+'-', pos+1, 0, -1);
            DFS(num, sum, path+num[pos]+'*', pos+1, 0, val*pre);
        }
    
        vector<string> addOperators(string num, int target) {
            if(num.size() ==0) return {};
            DFS(num, -target, "", 0, 0, 1);
            return result;
        }
    private:
        vector<string> result;
    };

  • 0
    Q

    if you pass num by reference, i.e., DFS(string &num,...
    the speed will improve to 248ms and defeat 91%


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.