Target Sum (#494)
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 form the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Company Tags: Amazon
Core Concept: Dynamic Programming, Backtracking, DFS