• ㊗️
• 大家
• offer
• 多多！

## 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.


## Code

class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();

helper(res,"", num, target, 0, 0, 0);
return res;
}

private void helper(List<String> res, String path, String num, int target, int pos, long val, long pre){
if(pos == num.length()){
if(target == val){
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));

if(pos == 0){
helper(res, path + cur, num, target, i + 1, cur, cur);
} else{
helper(res, path + "+" + cur, num, target, i + 1, val + cur, cur);
helper(res, path + "-" + cur, num, target, i + 1, val - cur, -cur);
helper(res, path + "*" + cur, num, target, i + 1, val - pre + pre * cur, pre * cur);
}
}
}
}