Frontend School

Expression Target Sum

DSA
hard

Expression Target Sum

Hard
Backtracking
String
Math

Overview

In many computing contexts, from compilers to financial modeling tools, the ability to parse and evaluate mathematical expressions is fundamental. A related challenge is to reverse-engineer expressions that yield a specific target value. This problem explores how to construct such expressions from a given sequence of digits, leveraging basic arithmetic operations.

What you need to do / Task

Your task is to implement a function that finds all possible valid mathematical expressions by inserting binary operators (+, -, *) between the digits of a given string num such that the expression evaluates to a target value.

  1. Implement the function addOperators which takes a string num (composed of digits '0'-'9') and an integer target.
  2. The function should return a list of strings, where each string is a valid expression that evaluates to target.
  3. Numbers formed by concatenating digits can be multi-digit (e.g., '1' and '2' can form '12'). However, a number cannot have leading zeros unless the number itself is '0' (e.g., '05' is invalid, but '0' is valid).
  4. Standard operator precedence applies: multiplication (*) has higher precedence than addition (+) and subtraction (-).

Input & output

  • num: A string consisting only of digits ('0'-'9').
  • target: An integer representing the desired evaluation result.
  • Returns: string[]. A list of strings, where each string is a valid expression. The order of expressions in the output list does not matter. If no such expressions exist, return an empty list.

Clarifications

  • The target value can be negative.
  • If num is a single digit, say "5", and target is 5, then the output should be ["5"].
  • The problem specifically asks for binary operators, meaning each operator connects two numbers (or sub-expressions).

Examples

1

Example 1

Input:

num = "123", target = 6

Output:

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

Note:

For "123" and target 6, both "1+2+3" (1+2+3=6) and "123" (123=6) are valid expressions.

2

Example 2

Input:

num = "232", target = 8

Output:

["23+2","2+32"]

Note:

For "232" and target 8, "23+2" (6+2=8) and "2+32" (2+6=8) are valid expressions. Note that operator precedence is applied.

3

Example 3

Input:

num = "105", target = 5

Output:

["1*0+5","10-5"]

Note:

For "105" and target 5, "10+5" (0+5=5) and "10-5" (10-5=5) are valid. "105" would be invalid due to the leading zero in '05'.

4

Example 4

Input:

num = "00", target = 0

Output:

["0+0","0-0","0*0"]

Note:

For "00" and target 0, only single '0's can be parsed. "00" as a number is invalid. Thus, "0+0", "0-0", and "0*0" are valid.

Constraints

Constraints & assumptions

  • 1 <= num.length <= 10
  • num consists only of digits '0'-'9'.
  • -2^31 <= target <= 2^31 - 1
  • Intermediate and final results of expressions will fit within a 64-bit signed integer type (e.g., long in Java/C#, number in JavaScript/TypeScript).

What interviewers evaluate

  • Correctness of Backtracking Logic: The ability to systematically explore all valid combinations of operators and numbers, handling base cases and recursive steps accurately.
  • Operator Precedence: Proper implementation of arithmetic rules, specifically how multiplication interacts with addition and subtraction.
  • Number Parsing & Edge Cases: Correctly forming multi-digit numbers from num and adhering to the 'no leading zeros' rule (unless the number is '0' itself).
  • Efficiency: Managing intermediate states (current expression string, current evaluation, last operand value) efficiently to avoid redundant computations.
  • Code Clarity: Writing clean, readable, and well-structured code that is easy to understand and debug.

Loading editor...