Katkat
Back

Count expressions reaching a target sum

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count expressions reaching a target sum states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an array of non-negative integers nums and an integer target T, assign either a + or − sign to each number to form an expression. Count how many distinct sign assignments evaluate exactly to T. Implement a correct solution and compare recursion with memoization vs iterative dynamic programming; analyze time and space complexity. Discuss handling zeros, large sums, and how to return one valid assignment if it exists.