282. Expression Add Operators

Problem

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:

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:

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:

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

Solution

/**
 * @param {string} num
 * @param {number} target
 * @return {string[]}
 */
var addOperators = function(num, target) {
     var res = [];
     compute(num, "", 0, 0);
     return res;

     function compute(nums, exp, val, back){
         var tmp;
         if(nums === "" && val === target){
             res.push(exp);
         }else{
             for(var i = 1; i <= nums.length; i++){
                 var head = nums.substring(0, i);
                 var tail = nums.substring(i, nums.length);
                 var curr = parseInt(head) || 0;
                 if(head.length >= 2 && head[0] === "0"){
                     return;
                }
                 if(exp === ""){
                     compute(tail, head, curr, curr);
                 }else{
                     compute(tail, exp + "+" + head, val + curr, curr);
                     compute(tail, exp + "-" + head, val - curr, -1 * curr);
                     compute(tail, exp + "*" + head, val - back + back * curr, back * curr);                    
                 }
             }
         }
     }
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).