Expression Add Operators

IF
AlgoAxiomStaff Engineers
JSTS
Hard20 mins

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Examples

Example 1

Input: num = "123", target = 6

Output: ["1*2*3","1+2+3"]

Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2

Input: num = "232", target = 8

Output: ["2*3+2","2+3*2"]

Explanation: "2*3+2" = 8 and "2+3*2" = 2+6 = 8.

Example 3

Input: num = "3456237490", target = 9191

Output: []

Explanation: No combination of operators produces 9191.

Constraints

  • 1 <= num.length <= 10
  • num consists of only digits
  • -2³¹ <= target <= 2³¹ - 1
Source: Backtracking pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle