Expression add operators: place + and - between digits to reach a target

Take the digits 1 to 9 in order, as the string "123456789". Between each pair of neighboring digits, put +, -, or nothing (joining the digits into a longer number). You may also put + or - before the first digit. Given a target, find an expression that evaluates to it, or all of them.

Interface

Unless you agree on a different interface with the interviewer, assume:

• find_expression(target: int) -> str — one expression that evaluates to target, or "" if none exists.
• all_expressions(target: int) -> list[str] — every such expression.

Example

find_expression(100)      ->  "123+45-67+8-9"       # any valid expression is accepted
                              # others: "1+2+3-4+5+6+78+9", "-1+2-3+4+5+6+78+9"
len(all_expressions(100)) ->  12
find_expression(0)        ->  "12+34-56-7+8+9"      # or another valid one
find_expression(99999)    ->  ""

Constraints

• The digits are fixed: "123456789". -10^9 <= target <= 10^9.
• Evaluate as you build. Do not create every string and parse it afterwards.

Clarifying questions

• Is a leading sign before the first digit allowed?
• One expression, all of them, or only whether one exists?
• Are other operators allowed, such as *?
• Should the digits be a parameter, possibly including 0?

What a strong answer covers

• Backtracking over the 8 gaps with three choices each (3⁸ = 6,561 expressions, times 2 for a leading -). Carry the running total and the signed value of the number being built.
• Joining a digit without reparsing: subtract the current operand from the total and add back sign * (operand * 10 + d).
• Pruning: stop a branch when even the largest possible remaining contribution cannot reach the target.
• With general digits: never allow a number with a leading zero, such as 05.
• 64-bit arithmetic for long concatenations in fixed-width languages.

Follow-ups

• Take any string of digits and also allow *. Multiplication binds tighter, so carry the last operand to undo it.
• Count the expressions instead of listing them, with memoization.
• Return the expression with the fewest operators.