Simple C++ recursion (with enough comments)


  • 0
    G
        void _addOperators(string& num, int idx, long target, string ans, long last_val, vector<string>& res) {
            if (target == 0 && idx == num.size()) {
                res.push_back(ans);
                return;
            }
            for (int i = idx; i < num.size(); i++) {
                if (num[idx] == '0' && i != idx) break;     // '0y' is invalid
                
                string cur_str = num.substr(idx, i - idx + 1);
                long cur_val = stol(cur_str);
                
                if (idx == 0) {
                    // the very first guy won't have any operator infront of it
                    _addOperators(num, i + 1, target - cur_val, cur_str, cur_val, res);
                } else {
                    _addOperators(num, i + 1, target - cur_val, ans + "+" + cur_str, cur_val, res);
                    _addOperators(num, i + 1, target + cur_val, ans + "-" + cur_str, -cur_val, res);
                    // '*' is the tricky case, let's look at an example.
                    // If 'num' is "123" and so far we did 1+2 ('last_val' is +2) and now we want to do 1+2*3, the idea is
                    // we first increment the 'target' by whatever we decremented in the last call. The rest is as usual
                    _addOperators(num, i + 1, target + last_val - last_val*cur_val, ans + "*" + cur_str, last_val * cur_val, res);
                }
            }
        }
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            if (num.empty()) return res;
            
            _addOperators(num,                              /* input num */
                          0                                 /* idx in 'num' */,
                          target                            /* updated target */,
                          ""                                /* answer string so far */,
                          0                                 /* what we did in this call becomes 'last_val' for next call */,
                          res                               /* set of answers */);
            
            return res;
        }
    

Log in to reply
 

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