Leetcode 282 Solution

This article provides solution to leetcode question 282 (expression-add-operators)

https://leetcode.com/problems/expression-add-operators

Solution

class Solution { vector<string> res;
public: void addOperators(const string& num, int i, int64_t diff, int64_t target, int64_t curr, string curr_exp) { if (i == num.size()) { if (curr == target) res.push_back(curr_exp); return; }
for (int j = i; j < num.size(); j++) { string var = num.substr(i, j - i + 1); int64_t ivar = atoll(var.c_str());
if (to_string(ivar) != var) continue;
if (i == 0) { addOperators(num, j + 1, ivar, target, ivar, var); } else { addOperators(num, j + 1, ivar, target, curr + ivar, curr_exp + "+" + var); addOperators(num, j + 1, -ivar, target, curr - ivar, curr_exp + "-" + var); addOperators(num, j + 1, ivar * diff, target, curr - diff + diff * ivar, curr_exp + "*" + var); } } }
vector<string> addOperators(string num, int target) { addOperators(num, 0, 0, target, 0, ""); return res; } };