Expression Add Operators

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;
    }
}
comments powered by Disqus