cpp-flashcards/org/study_deck_02/dsa/2-d-dynamic-programming/0494-target-sum.org

#+ANKI_DECK: study_deck_02
* TODO 0494. Target Sum :medium:
:PROPERTIES:
:NEETCODE: [[file:../../roadmap.org::*0494. Target Sum][0494. Target Sum]]
:END:

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~.

*Example 1:*


#+begin_src
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
#+end_src


*Example 2:*


#+begin_src
Input: nums = [1], target = 1
Output: 1
#+end_src


*Constraints:*

 - ~1 <= nums.length <= 20~

 - ~0 <= nums[i] <= 1000~

 - ~0 <= sum(nums[i]) <= 1000~

 - ~-1000 <= target <= 1000~

** TODO Approach
Write your approach here.

** TODO Python
#+begin_src python :lc-problem 494 :lc-lang python3
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
#+end_src

** TODO C++
#+begin_src cpp :lc-problem 494
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        
    }
};
#+end_src