How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Count expressions reaching a target sum

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.

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.

Input: ([1], 2)

Expected Output: 0

Explanation: |target| = 2 > total = 1, so no sign assignment can reach 2.

Input: ([100], -200)

Expected Output: 0

Explanation: |target| = 200 > total = 100; impossible.

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

Expected Output: 256

Explanation: The 1 must be +. Each of the 8 zeros can be + or - freely, contributing 2^8 = 256 distinct assignments. s = (1+1)/2 = 1 and the DP multiplies by 2 per zero.

Input: ([2, 3, 5, 7, 9], 4)

Expected Output: 1

Explanation: s = (26+4)/2 = 15. The only subset summing to 15 is {3,5,7}, i.e. +3+5+7-2-9 = 4. So exactly 1 assignment.

Input: ([], 0)

Expected Output: 1

Explanation: Empty expression evaluates to 0; the one (empty) assignment matches. s = 0, dp[0] = 1.

Input: ([], 1)

Expected Output: 0

Explanation: Empty expression can only be 0, never 1. |target| > total = 0 -> 0.

Hints

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.
Adding the two equations gives sum(P) = (total + target) / 2. If (total + target) is odd or |target| > total, no assignment works -> return 0.
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.
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.

Quick Overview