Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
例子
例子 1
Input: num = "123", target = 6 Output: ["1+2+3", "1*2*3"]
例子 2
Input: num = "232", target = 8 Output: ["2*3+2", "2+3*2"]
例子 3
Input: num = "105", target = 5 Output: ["1*0+5","10-5"]
private: std::vector<std::string> m_result; int m_target;
voidgeneratePath(conststd::string& num, int idx, std::string& path, long curr_eval, long prev_eval){ if (idx == num.length()) { if (curr_eval == m_target) { m_result.push_back(path); } return; }
long candidate = 0; for (int i = idx; i < num.length(); ++i) { if (i != idx && num[idx] == '0') break; // number begins with 0 and not 0 (e.g 01) is invalid
candidate *= 10; candidate += (num[i] - '0');
std::string candidate_str = std::to_string(candidate); if (idx == 0) { // if this is the beginning of path, (e.g path == ""), no previous operator is required path += candidate_str; generatePath(num, i + 1, path, candidate, candidate); path.erase(path.length() - candidate_str.length()); } else { // #1 : addition path += "+"; path += candidate_str; generatePath(num, i + 1, path, curr_eval + candidate, candidate); // #2 : substraction path[path.length() - candidate_str.length() - 1] = '-'; generatePath(num, i + 1, path, curr_eval - candidate, - candidate);