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)) answer = [] # 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: answer.append(prevArrangement + str(lon[start])) 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, "") return answer |
---|

eg : ans = Solution()

num = "123", target = 6

ans.addOperators(nums, target)

**Output -**

**["1+2+3", "1*2*3"] **