C++ 156ms 18 lines


  • 0
    class Solution {
    private:
        vector<string> ans;
        
        // start: start position in num; sum: latest sum without last number; lastNum: the last number to be added to sum
        void search(string& num, int start, int& target, string path, long sum, long lastNum) {
            if (start == num.length()) {
                if (sum + lastNum == target) { ans.push_back(path); }           // record path if evaluation equals target
                return;
            }
            
            // only one digit allowed if num[start] == '0'
            for (long end = start, curNum = 1; curNum != 0 && end < num.length(); end++) {  
                string curStr = num.substr(start, end - start + 1);
                curNum = stol(curStr);
                
                search(num, end + 1, target, path + '+' + curStr, sum + lastNum, curNum);
                search(num, end + 1, target, path + '-' + curStr, sum + lastNum, -curNum);
                search(num, end + 1, target, path + '*' + curStr, sum , lastNum * curNum);
            }
        }
    
    public:
        vector<string> addOperators(string num, int target) {
            for (long end = 0, curNum = 1; curNum != 0 && end < num.length(); end++) {      // first number is special case
                search(num, end + 1, target, num.substr(0, end + 1), 0, curNum = stol(num.substr(0, end + 1)));
            }
            return ans;
        }
    };
    

Log in to reply
 

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