# Leetcode Expression Add Operators (Java)

Tags: ,

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:

Analysis:

This problem can be solved using DFS algorithm. For example, given the input “`123456`“, suppose we encounter the last digit “6”, at which we already have the result of solve(“`12345`“). Then there are three cases:

solve(“123456”) = solve(“12345”) + 6

solve(“123456”) = solve(“12345”) – 6

solve(“123456”) = cal( solve(“12345”) , 6, *), this have the following three cases:

1. suppose solve(“12345”) = solve(“1234”) + 5,  so we have solve(“123456”) = solve(“`1234`“) + `5` * 6
2. suppose solve(“12345”) = solve(“123”) + 4  * 5,  so we have solve(“123456”) = solve(“`123`“) + `4 * 5` * 6
3. suppose solve(“12345”) = solve(“1234”)  –  5,  so we have solve(“123456”) = solve(“`1234`“) `- 5` * 6.

From the above three cases , we can see that in the step of solve(“`123456`“), we already have solve(“`12345`“), we also need to have the value of solve(“`1234`“), and `5` for case 1, 3; and solve(“123”) and `4*5` for case 2.

In the above case 1, we define preSum = solve(“1234”) + 5, and preVal = 5, then we have solve(“1234”) = solve(“12345”) – 5 = preSum – preVal.

In the above case 2, we define preSum = solve(“123”) + 4*5 ,and preVal = 4 * 5, then we have solve(“123”) = solve(“12345”) – 4*5 = preSum – preVal.

in the above case 3, we define preSum = solve(“1234”) – 5, and preVal = -5, then we have solve(“1234”) = solve(“12345”) – (-5) = preSum – preVal.

So in the recursive process, we need to track the `preSum`, and `preVal` based on the operators. See the following Java implementation for details.