Katkat
Back

Build an Expression That Reaches a Target

WaymoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use recursion with backtracking or dynamic programming to partition a sequence of numbers and apply operators to satisfy a target value.

Problem Description

Given a list of non-negative integers nums and an integer target, you need to construct a fully parenthesized mathematical expression using all the numbers in the original order. You must use the operators +, -, and * exactly once for each adjacent pair (resulting in n-1 operators total).

Your goal is to return the lexicographically smallest fully parenthesized expression that evaluates to the target. If no such expression exists, return an empty string.

Constraints

  • 2 <= len(nums) <= 8
  • 0 <= nums[i] <= 100
  • target is an integer.
  • Fully parenthesized means every operation must be enclosed in parentheses, e.g., ((1+2)*3).

Examples

Example 1: Input: nums = [1, 2, 3], target = 9 Output: ((1+2)*3) Explanation: 1+2 = 3, 3*3 = 9. This is the only valid construction.

Example 2: Input: nums = [2, 2], target = 4 Output: (2*2)

Edge Cases

  • If nums has only one element, return the number as a string only if it matches the target.
  • If multiple valid expressions exist, the lexicographically smallest string (e.g., ((1+2)*3) vs ((1*3)+2)) is chosen.

Hints

Hint 1

Use recursion to break the array into two sub-problems at every possible split point.

Hint 2

For each split, recursively find all possible results of the left and right subarrays, then combine them using the three operators.

Hint 3

Since the input size is small (up to 8), you can store results in a memoization table where the key is the index range `(i, j)` and the value is a list of all possible values and their corresponding expression strings.

Follow-up questions

  • How would your approach change if you were allowed to use parentheses arbitrarily instead of requiring them for every operation?
  • What is the time complexity of your solution, and can you optimize it if the list of numbers were significantly longer?
  • How would you handle division and ensure that all intermediate results remain integers?