Target sum
GoogleThe 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)
{
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question