This is a backtracking problem, very similar to palindrome partitioning.

We need to record prev and sum, so we can check if we’ve got the result quickly.

When +cur, prev = cur, sum += cur

When -cur, prev = -cur, sum -= cur.

When *cur, Like 1+2*3*4. sum = (sum - prev) + cur*prev as in (7 - 2*3) + 4*2*3. prev = prev*cur.

Question:

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 2 3 4

Input: num = "105", target = 5 Output: ["1*0+5","10-5"] Explanation: Both "1*0+5" and "10-5" evaluate to 5. Note that "1-05" is not a valid expression because the 5 has a leading zero.