# Expression Add Operators Problem

0 like 0 dislike
250 views

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.

Example 1:

```Input: `num = `"123", target = 6
Output: ["1+2+3", "1*2*3"]
```

Example 2:

```Input: `num = `"232", target = 8
Output: ["2*3+2", "2+3*2"]```

Example 3:

```Input: `num = `"105", target = 5
Output: ["1*0+5","10-5"]```

Example 4:

```Input: `num = `"00", target = 0
Output: ["0+0", "0-0", "0*0"]
```

Example 5:

```Input: `num = `"3456237490", target = 9191
Output: []
```

Constraints:

• `0 <= num.length <= 10`
• `num` only contain digits.

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

Given a number X, and a list of numbers lon = [N1, N2, ..., Nk], and a target number

F(X, lon, target) returns the combinations of "X * N1N2N3" that yields target, where the rules for inserting operator between digits is the same as problem described above

The only difference being there is a multiplication operator inserted after X already.

Our original problem asks for all possible arrangements of input lon such that each arrangement E satisfies Eval(E) = target. Well, by property 4, that is just a special case of the more generalized F, namely, F(1, lon, target).

We will show how to recursively apply F to compute the desired output. We do this by enumerating all cases based on the input.

Note: We denote lon as [N1, N2, ..., Nk]. Thus len(lon) = k

Base case

When k == 1, by definition of F, if X * N1 == target, this arrangement is qualified, and we return its string representation: str(X) + '*' + str(N1)

Recursive cases

Remember we can either insert one of the three operators, or not insert anything. Thus we have 4 cases:

Insert nothing

We keep N1 and N2 together in this case, but this only works if N1 is not '0', since something like '07' will not be a valid NumberString.

Assume that, and by definition of F, we can recursively compute the output as

F(X, [N1 * 10 + N2, N3, ..., Nk], target)

Insert +

The final arrangement will look like 'X * N1 + E', where E is whatever arrangement the rest of the lon ([N2, N3, ..., Nk]) came out to be.

Thus, we want this string to evaluate to target, meaning that,

Eval('X * N1' + '+' + E) = target. By property 1 we have:

target = Eval('X * N1') + Eval(E) = X * N1 + Eval(E)

In other words, we want Eval(E) = target - X * N1

What are the possible arrangements for that? That is precisely a subproblem to the original problem, thus the answer for that is

F(1, [N2, N3, ..., Nk], target - X * N1

Insert -

This is similar to the case with '+' above, because we can use property 2 to transform '-'.

We want Eval('X * N1' + '-' + E) = target. By property 2 we have:

target = Eval('X * N1') + Eval('-1*' + E) = X * N1 + Eval('-1*' + E)

In other words, we want Eval('-1*' + E) = target - X * N1

To solve this subproblem, we need to utilize the definition for F, which suggests that the answer is

F(-1, [N2, N3, ..., Nk], target - X * N1

Insert *

This follows the same pattern as the above cases.

We want Eval('X * N1' + '*' + E) = target. By property 3 we have:

target = Eval(str(Eval('X * N1')) + '*' + E)

By definition of F, we can derived the answer easily:

F(X * N1, [N2, N3, ..., Nk], target

class Solution:

def addOperators(self, num: str, target: int) -> List[str]:

lon = list(map(int, num))

# F is exactly like what we defined above, except it has

# an extra argument to keep track of the partial string arrangement (including 'X*')

# already determined as it recurs down the search

# Also lon is represented as lon[start:]

# Viable arrangement will be appened into @answer in string form

def F(x, start, targ, prevArrangement):

# notice that start increments on every recursive call, so termination is ensured.

if start == len(lon) - 1:

if x * lon[start] == targ:

return

#  case 1 (no operator insertion)

# we have to modify the value of lon[start + 1]

# so we restore its value after the function returns

if lon[start] != 0:

lon[start + 1] += lon[start] * 10

F(x, start + 1, targ, prevArrangement)

lon[start + 1] -= lon[start] * 10

# case 2, insert '+'

F(1, start + 1, targ - x*lon[start], prevArrangement + str(lon[start]) + '+')

# case 3, insert '-'

F(-1, start + 1, targ - x*lon[start], prevArrangement + str(lon[start]) + '-')

# case 4, insert '*'

F(x * lon[start], start + 1, targ, prevArrangement + str(lon[start]) + '*')

# since we don't want to keep the "1*" in the front, we initialize

# prevArrangement to be empty string.

F(1, 0, target, "")

eg : ans = Solution()

num = "123", target = 6  