Insert Plus or Times Between Ordered Numbers to Reach a Target, Evaluated Left to Right

You are given a list of nonnegative integers and a target. Decide whether you can place either + or * between every pair of adjacent numbers so that the resulting expression equals the target. The numbers must stay in their original order.

The expression is evaluated strictly from left to right, ignoring the usual operator precedence. For example, 2 + 3 * 4 evaluates as (2 + 3) * 4 = 20, not 14.

Function Signature

def can_reach_target(nums: list[int], target: int) -> bool:
    ...

Rules

• Exactly one operator, + or *, goes in each of the len(nums) - 1 gaps. Numbers cannot be concatenated, reordered, skipped, or negated, and no parentheses can be added.
• Evaluation starts with nums[0] as the running value. For each later index i, the running value becomes running + nums[i] or running * nums[i], depending on the operator in that gap.
• If nums has one element, there are no operators, and the answer is whether that element equals target.
• Return True if at least one assignment of operators produces exactly target. Otherwise, return False.

Constraints

• 1 <= len(nums) <= 10
• 0 <= nums[i] <= 30
• 0 <= target <= 10^15
• Intermediate and final values can exceed 2^31 - 1, but they never exceed 30^10 (about 5.9 * 10^14), so 64-bit integers are enough.

Examples

Input: nums = [2, 3, 4], target = 20

Output: True

(2 + 3) * 4 = 20.

Input: nums = [1, 2, 3], target = 7

Output: False

The four possible assignments give 1 + 2 + 3 = 6, (1 + 2) * 3 = 9, 1 * 2 + 3 = 5, and 1 * 2 * 3 = 6. With standard precedence, 1 + 2 * 3 would equal 7, but that evaluation order is not used here.

Input: nums = [5], target = 5

Output: True

Insert Plus or Times to Reach the Target

Hints

1. There are only len(nums) - 1 gaps and at most 10 numbers, so the total number of distinct operator assignments is small; you do not need a clever formula.
2. Because evaluation is strictly left to right, the only thing a prefix of the expression contributes to the rest of the computation is the single running value it produced.
3. Do not assume the running value only grows: multiplying by 0 collapses it and multiplying by 1 leaves it unchanged, so discarding a state merely because it already passed the target would lose real answers.

Approach

Because the expression is evaluated strictly left to right, a prefix of the expression is fully summarized by the single running value it produced: nothing about which operators were used matters afterwards. That gives a forward set-of-states scan.

Algorithm: start with the set {nums[0]}. For each later element value, replace the current set of running values R by { r + value : r in R } union { r * value : r in R }. After processing every element, return whether target is in the final set.

Invariant: after processing index i, the set contains exactly the values obtainable by evaluating nums[0..i] left to right under some assignment of operators to the i gaps before it. Base case: with i = 0 the only value is nums[0] (this also covers the single-element rule, where the answer reduces to nums[0] == target). Inductive step: any evaluation of nums[0..i+1] consists of an evaluation of nums[0..i] followed by exactly one operator applied with nums[i+1], and the two branches enumerate both choices; conversely every value produced by the step comes from a real prefix evaluation. So the final set is exactly the set of achievable expression values, and membership of target is the required answer.

Edge cases: a one-element list never enters the loop and correctly compares against nums[0]. Zeros matter in both directions: multiplying by 0 collapses the running value to 0, and adding 0 leaves it unchanged. Ones behave the same way (r * 1 == r while r + 1 != r). Because of that, the running value does NOT increase monotonically, so pruning states that already exceed target would be wrong -- a later multiply by 0 can bring any state back down to 0. The implementation therefore keeps every state. Values can exceed 2^31 - 1 (the maximum is 30^10 = 590490000000000), so Java uses long and C++ uses long long; all values stay below 2^53, so JavaScript numbers remain exact. Deduplicating states with a set is what keeps repeated values (e.g. many equal elements) cheap. A defensive empty-list guard returns False, though the constraints do not allow an empty list.

• Time complexity: O(2^n) -- at most 2^(n-1) distinct running values are tracked and each spawns two successors; with n = len(nums) <= 10 that is at most 512 operator assignments.
• Space complexity: O(2^n) for the set of reachable running values (at most 512 values here).