Quick Overview

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.

Count expressions reaching a target sum

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: 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 in front of each number to form an expression. Count how many distinct sign assignments make the expression evaluate exactly to T. Each element gets exactly one sign, and different sign assignments are counted as distinct even if they yield identical numeric concatenations (e.g. two equal numbers signed differently are two distinct assignments). Example: `nums = [1,1,1,1,1]`, `T = 3`. There are 5 ways: `-1+1+1+1+1`, `+1-1+1+1+1`, `+1+1-1+1+1`, `+1+1+1-1+1`, `+1+1+1+1-1`. Return `5`. Key idea: Let P be the set of elements given `+` and N the set given `-`. Then `sum(P) - sum(N) = T` and `sum(P) + sum(N) = total`, so `sum(P) = (total + T) / 2`. The answer is the number of subsets of `nums` summing to `s = (total + T) / 2` — solvable with a 0/1-knapsack-style count DP. If `total + T` is odd or `|T| > total`, the answer is 0. Note zeros do not change a subset sum but still count toward distinct assignments, so they naturally multiply the count by 2 each (a zero can be placed in P or N).

Constraints

  • 1 <= nums.length <= 20 (and the empty array is handled correctly)
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums) <= 1000
  • -1000 <= target <= 1000

Examples

Input: ([1, 1, 1, 1, 1], 3)

Expected Output: 5

Explanation: Exactly one of the five 1's gets a minus sign; the other four are plus. 5 choices -> 5 assignments. s = (5+3)/2 = 4, and there are C(5,4)=5 subsets of size 4 summing to 4.

Input: ([1], 1)

Expected Output: 1

Explanation: Only +1 reaches 1. s = (1+1)/2 = 1; one subset {1} sums to 1.

Hints

  1. Split nums into a positive set P (assigned +) and a negative set N (assigned -). Then sum(P) - sum(N) = target and sum(P) + sum(N) = total.
  2. Adding the two equations gives sum(P) = (total + target) / 2. If (total + target) is odd or |target| > total, no assignment works -> return 0.
  3. Now the problem is 'count subsets of nums that sum to s = (total + target) / 2' — a classic 0/1-knapsack counting DP. Iterate j downward so each number is used at most once.
  4. Zeros need care: a zero can go in P or N without changing any sum, so each zero doubles the number of distinct assignments. The subset-sum DP captures this automatically because dp[j-0] = dp[j] adds the count of placing the zero.

Loading coding console...