Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonFacebook

Target Sum

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a list of numbers and want to assign '+' or '-' signs to each so that the total equals a target sum. How many ways can you do this?

Given an array of integers nums and an integer target, return the number of different expressions that can be built by adding '+' or '-' before each integer such that the resulting expression evaluates to target. Input: nums (list of integers), target (integer) Output: integer representing the count of valid expressions.

1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 10000 ≤ sum(nums[i]) ≤ 1000-1000 ≤ target ≤ 1000
Edge cases: nums = [0,0,0,0,0], target = 0 → 32 (all combinations of + and - count)nums = [1000], target = 1000 → 1 (only +1000 works)nums = [1], target = 2 → 0 (no way to reach 2)
</>
IDE
def findTargetSumWays(nums: list[int], target: int) -> int:public int findTargetSumWays(int[] nums, int target)int findTargetSumWays(vector<int>& nums, int target)function findTargetSumWays(nums, target)
def findTargetSumWays(nums, target):
    # Write your solution here
    pass
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int findTargetSumWays(vector<int>& nums, int target) {
    // Write your solution here
    return 0;
}
function findTargetSumWays(nums, target) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 0Base case returns 0 instead of 1 when index == len(nums) and current sum == target.✅ Change base case to return 1 if current sum equals target at recursion end.
Wrong: 1Ignoring sign assignments for zeros, counting only one way instead of 2^count_of_zeros.✅ Branch on both + and - for zeros as well to count all combinations.
Wrong: Nonzero for impossible targetIncorrect base case or pruning allowing invalid sums to count.✅ Return 0 when sums do not match target at recursion end.
Wrong: Wrong count due to greedy approachGreedy sign assignment misses multiple valid ways.✅ Use DP or recursion to enumerate all sign assignments.
Wrong: TLEUsing brute force recursion without memoization for large n.✅ Implement memoization or bottom-up DP to reduce complexity to O(n*sum).
✓
Test Cases
t1_01basic
Input{"nums":[1,1,1,1,1],"target":3}
Expected5

There are 5 ways to assign signs to get sum 3: -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.

t1_02basic
Input{"nums":[2,3,1],"target":2}
Expected1

Only one way: -2+3+1=2. Other sign combinations do not yield target 2.

t2_01edge
Input{"nums":[],"target":0}
Expected1

Empty array with target 0 counts as one valid expression (empty sum).

t2_02edge
Input{"nums":[0,0,0,0,0],"target":0}
Expected32

Each zero can be +0 or -0, doubling ways each time: 2^5=32 ways.

t2_03edge
Input{"nums":[1000],"target":1000}
Expected1

Only +1000 matches target 1000; -1000 does not.

t3_01corner
Input{"nums":[1,2,3],"target":7}
Expected0

Target 7 cannot be formed by any combination of + or - signs on [1,2,3].

t3_02corner
Input{"nums":[1,1,1,1,1],"target":1}
Expected10

Multiple ways to assign signs to get sum 1, similar to canonical example but different target.

t3_03corner
Input{"nums":[1,2,3,4],"target":0}
Expected2

No combination of + or - signs on [1,2,3,4] sums to 0.

t4_01performance
Input{"nums":[1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10],"target":10}
⏱ Performance - must finish in 2000ms

n=20, sum(nums)=110, DP O(n*sum) ~ 2200 operations must complete within 2s.

Practice

(1/5)
1. You need to find the minimum number of perfect square numbers that sum to a given integer n. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming using unbounded knapsack pattern with bottom-up tabulation
B. Greedy approach picking the largest square first until the sum is reached
C. Simple recursion without memoization exploring all combinations
D. Sorting all squares and using binary search to find the closest sum

Solution

  1. Step 1: Understand problem constraints

    The problem requires the minimum count of perfect squares summing to n, which is a classic unbounded knapsack variant where items (squares) can be reused.
  2. Step 2: Identify algorithm that guarantees optimality

    Greedy fails because picking largest squares first can be suboptimal (e.g., n=12). Simple recursion is correct but inefficient. Binary search does not solve the combinatorial optimization. Bottom-up DP with unbounded knapsack pattern systematically explores all combinations and ensures optimality.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DP approach always finds minimum count [OK]
Hint: Greedy fails; DP unbounded knapsack guarantees optimal [OK]
Common Mistakes:
  • Assuming greedy works for minimum perfect squares
  • Confusing top-down recursion with guaranteed efficiency
2. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the coin change minimum coins problem, given n coins and amount S?
medium
A. O(n * S) because for each amount up to S, all n coins are checked
B. O(n^S) due to exploring all combinations recursively
C. O(S^2) since the dp array is updated for each sub-amount multiple times
D. O(n + S) as the algorithm iterates once over coins and once over amounts

Solution

  1. Step 1: Identify loops in the bottom-up DP

    Outer loop runs from 1 to S (amount), inner loop runs over n coins.
  2. Step 2: Calculate total operations

    Each dp[i] is updated by checking all n coins, so total operations = n * S.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Nested loops over amount and coins -> O(n * S) [OK]
Hint: Nested loops over amount and coins yield O(n*S) [OK]
Common Mistakes:
  • Confusing recursion exponential time with DP
  • Assuming quadratic due to dp updates
3. What is the time complexity of the optimal bottom-up dynamic programming solution for the problem, given strs has length l, and the constraints are m zeros and n ones?
medium
A. O(l * (m + n))
B. O(l * m * n)
C. O(l * m * n * max_length_of_string)
D. O(2^l)

Solution

  1. Step 1: Identify loops in the code

    Outer loop iterates over all strings (l), inner loops iterate over m and n capacities.
  2. Step 2: Calculate total operations

    Each string causes updates over a 2D dp array of size (m+1)*(n+1), so total complexity is O(l * m * n).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nested loops over l, m, n -> O(l * m * n) [OK]
Hint: Nested loops over strings and both capacities multiply complexities [OK]
Common Mistakes:
  • Confusing sum with product of m and n
  • Including string length in complexity unnecessarily
4. Suppose the stones can be used multiple times (unlimited quantity of each stone). Which modification to the DP approach correctly computes the minimal last stone weight?
hard
A. Use a greedy approach smashing largest stones repeatedly
B. Keep the inner loop iterating backwards as in 0/1 knapsack to avoid reuse
C. Change the inner loop to iterate forwards from weight to half, allowing reuse of stones
D. Use recursion without memoization to explore all combinations with reuse

Solution

  1. Step 1: Understand difference between 0/1 and unbounded knapsack

    For unlimited reuse, inner loop must iterate forwards to allow multiple counts of the same stone.
  2. Step 2: Modify DP accordingly

    Iterating forwards from weight to half updates dp[w] using dp[w - weight] from the same iteration, enabling reuse.
  3. Step 3: Why other options fail

    Backward iteration prevents reuse; greedy is incorrect; recursion without memoization is inefficient.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Forward iteration in inner loop enables unlimited stone reuse [OK]
Hint: Unbounded knapsack -> inner loop forwards [OK]
Common Mistakes:
  • Using backward iteration causing no reuse
  • Trying greedy which is incorrect
  • Ignoring memoization leading to TLE
5. Suppose the problem is modified so that each ticket can be used multiple times but only on distinct travel days (no overlapping coverage). Which modification to the algorithm is necessary to handle this constraint correctly?
hard
A. Use a top-down DP with memoization and add a visited set to track used tickets
B. Change binary search to linear scan to find next uncovered day to avoid reuse overlap
C. Modify DP state to include the last day covered and ensure no overlapping ticket durations
D. No change needed; the existing bottom-up DP with binary search works as is

Solution

  1. Step 1: Understand new constraint

    Tickets can be reused but cannot overlap coverage on travel days. This requires tracking coverage intervals explicitly.
  2. Step 2: Modify DP state

    DP must include last covered day or interval to ensure no overlapping coverage. Without this, DP may double count days or reuse tickets incorrectly.
  3. Step 3: Evaluate other options

    Adding visited sets or linear scans is inefficient or insufficient. Existing DP assumes unlimited overlapping coverage, so no change is incorrect.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    DP state must track coverage to prevent overlap [OK]
Hint: Track coverage intervals in DP state for reuse constraints [OK]
Common Mistakes:
  • Assuming no change needed
  • Using visited sets without DP state change
  • Replacing binary search with linear scan
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard