You are given a string num made only of digits, and a whole number target.
Put one of the signs '+', '-' or '*' between some of the digits of num, or put nothing between them. Find every expression that you can build this way whose value is exactly target.
A number inside an expression must not start with a zero, unless it is just the single digit 0. For example, 05 is not allowed.
Return all matching expressions as a list of strings. You may return them in any order.
Examples
Example 1:
Input: num = "303", target = 6
Output: ["3+0+3","3-0+3"]
Explanation: 3+0+3 and 3-0+3 both give 6. A number like "03" is not allowed.
Example 2:
Input: num = "222", target = 6
Output: ["2+2+2","2+2*2","2*2+2"]
Explanation: 2+2+2, 2*2+2 and 2+2*2 all give 6.
Example 3:
Input: num = "12", target = 100
Output: []
Explanation: Only 1+2, 1-2, 1*2 and 12 are possible, and none gives 100.