Coding

Target sum

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array nums of n integers and an integer target, build an expression using the integers from nums where each integer can be prefixed with either a '+' or '-' sign.

The goal is to achieve the target sum by evaluating all possible combinations of these signs.

Determine the number of ways to achieve the target sum and return your answer with modulo 109+7.

Input: nums = [1, 2, 7, 1, 5], target = 4 Output: 2 Explanation: There are 2 ways to assign symbols to make the sum of nums be target 4. +1 + 2 + 7 - 1 - 5 = 4 -1 + 2 + 7 + 1 - 5 = 4

Input: nums = [1], target = 1 Output: 1 Explanation: There is only one way to assign symbols to make the sum of nums be target 1.

Input: nums = [2, 1, 3, 1, 2], target = 2

1 ≤ n ≤ 100
0 ≤ nums[i] ≤ 1000
0 <= sum(A[i]) <= 104
-1000 <= target <= 1000

cpp

class Solution {
  public:
  int targetSum(int n, int target, vector<int>& nums) {
  
 }
};

java

class Solution {
    public int targetSum(int n, int target, int[] nums) {
     
    }
}

python

class Solution:
    def targetSum(self, n, target, nums):

javascript

class Solution {
    targetSum(n, target, nums) {
        
    }
}

csharp

class Solution
{
    public int targetSum(int n, int target, int[] nums)
    {
     
    }
}

func targetSum(n int, target int, nums []int) int {

}

Stuck? Show a way to structure it+

01Let P be numbers assigned plus and N those assigned minus.
02Derive `P=(sum+target)/2`.
03Reject when absolute target exceeds sum or the parity is odd.
04Count subsets with sum P using 0/1 DP in descending order.

Reference answer

If P is the sum of plus-signed numbers and N the sum of minus-signed numbers, then P-N=target and P+N=sum, so P=(sum+target)/2. There are no solutions if abs(target)>sum or sum+target is odd. Otherwise count subsets whose sum is P: initialize dp[0]=1, and for each number update sums downward so every number is used once. Zeros need no special branch: they correctly double every existing count because choosing either sign yields the same sum. Time is O(n*sum), space O(sum), with modulo arithmetic as required.

Then expect these follow-ups

How would you return one valid sign assignment?
Tests: reconstruction
Why does the reduction preserve the number of assignments?
Tests: algebraic proof

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question