Decide Target via Subsequence Plus/Multiply Expression
Given an array of positive integers nums and a target T: can you choose a subsequence (keep relative order, at least one element) and insert + or * between consecutive chosen elements — standard precedence, * binds first — so the expression equals T?
canReachTarget([2, 3, 5], 11) -> true // 2*3 + 5 canReachTarget([2, 3, 5], 17) -> true // 2 + 3*5 canReachTarget([2, 3, 5], 13) -> false // no subsequence works
Hints
Hint 1
Handle precedence with the (total, last) state from Expression Add Operators: the true value is total + last, where last is the pending product. Adding v commits the product (total += last, last = v); multiplying extends it (last *= v).
Hint 2
Layer subsequence choice on top: at each index either skip, start here if nothing is chosen yet, or extend with + or *. Memoize visited (index, total, last, started) states — the search is exponential in the worst case, and saying so is expected.