Insert the Operators

You are given a string of digits digits and a whole number target. Between each pair of neighbouring digits you may put +, -, * or nothing at all; putting nothing joins the digits into a longer number. Write hit_target(digits, target) that returns every expression you can make this way whose value is exactly target.

The usual order of operations applies: * is worked out before + and -. A number with more than one digit may not start with 0, so 05 is not allowed but 0 on its own is. No sign goes in front of the first number.

Return the expressions as strings with no spaces, sorted in Python's normal string order, or an empty list if there are none.

Examples

hit_target("234", 10)   # returns ['2*3+4']
hit_target("205", 5)    # returns ['2*0+5']
hit_target("1111", 2)   # returns ['1*1*1+1', '1*1+1*1', '1+1*1*1', '1+1+1-1', '1+1-1+1', '1-1+1+1']
hit_target("99", 1)     # returns []

Constraints

• 1 <= len(digits) <= 10
• -10**9 <= target <= 10**9