Insert plus, times and parentheses to reach a target

You are given an equation whose left side is a sequence of non-negative integers with no operators between them, and whose right side is a target. For example: 2 3 4 = 20.

Insert + or * between every pair of adjacent numbers, and add parentheses if you need them, so that the left side evaluates to the target. Standard precedence applies: parentheses first, then *, then +. You may not reorder, drop, or merge the numbers.

Implement:

def fill_equation(equation: str) -> str: ...

• The input is "<n1> <n2> ... <nk> = <target>", with numbers separated by spaces.
• Return the completed equation as one string with no spaces, such as "(2+3)*4=20".
• Use parentheses only where necessary: never add a pair that does not change the value under normal precedence. If several answers exist, return one with the fewest parentheses.
• Return "" if no placement of operators and parentheses reaches the target.

Constraints: 1 <= k <= 12, each number is between 0 and 100, and 0 <= target <= 10^4.

Example 1

Input:  "2 3 4 = 20"
Output: "(2+3)*4=20"

2+3*4 is 14 and 2*3+4 is 10, so a pair of parentheses is required.

Example 2

Input:  "1 2 3 4 = 21"
Output: "1+(2+3)*4=21"

Example 3

Input:  "2 2 2 2 = 32"
Output: ""

The largest reachable value is 16.

Reconstructed from the reported question; details may differ from what interviewers ask.