Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

174. Target Sum

MediumDay 51 of 60Dynamic Programming

You are given an integer array nums and an integer target. Put either a + or a - sign in front of every number and then add them all up. Return the number of different sign assignments whose result equals target.

Example 1
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Exactly one of the five 1s gets a minus sign, and there are 5 ways to choose which.
Example 2
Input: nums = [1], target = 1
Output: 1
Constraints
  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums) <= 1000
  • -1000 <= target <= 1000
Hints
Frequently asked at: Meta, Amazon, Google
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min