## Description

LeetCode Problem 282.

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators ‘+’, ‘-‘, and/or ‘*’ between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

 1 2 3 Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"] Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

 1 2 3 Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

 1 2 3 4 Input: num = "105", target = 5 Output: ["1*0+5","10-5"] Explanation: Both "1*0+5" and "10-5" evaluate to 5. Note that "1-05" is not a valid expression because the 5 has a leading zero.

Example 4:

 1 2 3 4 Input: num = "00", target = 0 Output: ["0*0","0+0","0-0"] Explanation: "0*0", "0+0", and "0-0" all evaluate to 0. Note that "00" is not a valid expression because the 0 has a leading zero.

Example 5:

 1 2 3 Input: num = "3456237490", target = 9191 Output: [] Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

• 1 <= num.length <= 10
• num consists of only digits.
• -2^31 <= target <= 2^31 - 1

## Sample C++ Code

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: vector ans; string s; int target; vector addOperators(string s, int target) { this->s = s; this->target = target; backtrack( 0, "", 0, 0); return ans; } void backtrack(int i, const string& path, long resSoFar, long prevNum) { if (i == s.length()) { if (resSoFar == target) ans.push_back(path); return; } string numStr; long num = 0; for (int j = i; j < s.length(); j++) { if (j > i && s[i] == '0') break; // Skip leading zero number numStr += s[j]; num = num * 10 + s[j] - '0'; if (i == 0) { backtrack(j + 1, path + numStr, num, num); // First num, pick it without adding any operator! } else { backtrack(j + 1, path + "+" + numStr, resSoFar + num, num); backtrack(j + 1, path + "-" + numStr, resSoFar - num, -num); backtrack(j + 1, path + "*" + numStr, resSoFar - prevNum + prevNum * num, prevNum * num); // Can imagine with example: 1-2*3 } } } };