bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium1-D Dynamic ProgrammingLC 494

Target Sum

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers. For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1 ". Return the number of different expressions that you can build, which evaluates to target.

Asked at 6 companies
AdobeAmazonBloomberg
Hints
  • 1.Think about what data structure fits Target Sum
  • 2.Consider the brute force complexity and how to optimize
  • 3.Can you trade space for time?
LeetCodeNeetCode