# Why my solution cannot pass "123456789", "45"

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

``````    for(int i = 1; i<= num.length(); i++){
long leftSide = Long.valueOf(num.substring(0,i));
String subRes = "" + (int)leftSide;
dfs(res, num, target, i, subRes, leftSide, leftSide, '#');
}

return res;
}

public static void dfs(List<String> res, String num, int target, int index, String subRes, long currentValue, long preLeft, char sign){
if(index == num.length() && (int)currentValue == target){
return;
}
for(int i = index + 1; i <= num.length(); i ++){
long rightValue = Long.valueOf(num.substring(index, i));
dfs(res, num, target, i, subRes + "+" +  rightValue, currentValue + rightValue, rightValue, '+');
dfs(res, num, target, i, subRes + "-" +  rightValue, currentValue - rightValue, rightValue, '-');
long newLeft;
if(sign == '-'){
newLeft = currentValue + preLeft - preLeft * rightValue;
}else if(sign == '+'){
newLeft = currentValue - preLeft + preLeft * rightValue;
}else {
newLeft = currentValue * rightValue;
}
dfs(res, num, target, i, subRes + "*" +  rightValue, newLeft, newLeft, sign);
}

}``````

• Your solution is wrong. Let's consider the expression `"1+2-34*5*6-7*89"` when your algorithm evaluates it. Let 's use Dry Run Table to trace your algorithm.

``````currentValue  preleft  sign  |  rightValue  subRes            newLeft
1               1       #    |  2           1
1+2 = 3         2       +    |  34          1+2
3-34 = -31      34      -    |  5           1+2-34            -31+34-34*5=-167
-167            -167    -    |  6           1+2-34*5          -167-167+167*6=668
668             668     -    |  7           1+2-34*5*6
668-7=661       7       -    |  89          1+2-34*5*6-7      661+7-7*89=45
45              45      -    |  _           1+2-34*5*6-7*89
``````

Your dfs yields the final result is 45, which is wrong because `1+2-34*5*6-7*89=-1640`.
You can check other solutions in the discussion threads to correct your solution ^_^

• dfs(res, num, target, i, subRes + "*" + rightValue, newLeft, newLeft, sign);

should be dfs(res, num, target, i, subRes + "*" + rightValue, newLeft, preLeft * rightValue, sign);

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.