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.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
Solution:
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
helper(ans, "", num, 0, target, 0, 0);
return ans;
}
public void helper(List<String> ans, String trial, String num, int pos, long target, long curVal, long curMul){
if(pos==num.length() && curVal==target){
ans.add(trial);
return;
}
for(int i=pos; i<num.length(); i++){
if(i!=pos && num.charAt(pos)=='0') return;
String curNum = num.substring(pos, i+1);
long curNumVal = Long.valueOf(curNum);
if(pos==0){
helper(ans, curNum, num, i+1, target, curNumVal, curNumVal);
} else {
helper(ans, trial + "+" + curNum, num, i+1, target, curVal + curNumVal, curNumVal);
helper(ans, trial + "-" + curNum, num, i+1, target, curVal - curNumVal, -curNumVal);
helper(ans, trial + "*" + curNum, num, i+1, target, curVal - curMul + curMul * curNumVal, curMul * curNumVal);
}
}
return;
}
}