Expression Add Operators


#1

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.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

#2

The below code uses backtracking to exhaustively search for all possible combinations of numbers and put in the operator between them.

public class Solution {
    public List<String> addOperators(String num, int target) {
      List<String> result = new ArrayList<>();
      if(num==null || num.length()==0) return result;
      StringBuilder expr = new StringBuilder();
      helper(num, target,result,expr, 0, 0, 0);
      return result;
    }
    
    private void helper(String num, int target, List<String> result, StringBuilder expr, int pos, long eval, long last){
        if(pos == num.length()){
            if(target == eval)
                result.add(expr.toString());
            return;
        }
        
        for(int i=pos;i<num.length();i++){
            if(i!=pos && num.charAt(pos)=='0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            int len = expr.length();
            if(pos==0){
                helper(num, target, result, expr.append(cur), i+1, cur, cur);
                expr.setLength(len);
            } else{
                helper(num, target, result, expr.append("+").append(cur), i+1, eval+cur, cur);
                expr.setLength(len);
                helper(num, target, result, expr.append("-").append(cur), i+1, eval-cur, -cur);
                expr.setLength(len);
                helper(num, target, result, expr.append("*").append(cur), i+1, eval-last+last*cur, last*cur);
                expr.setLength(len);
            }
        }
    }
}