## DEV Community

Abhishek Chaudhary

Posted on

# 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`.

Example 1:

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

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

• `1 <= nums.length <= 20`
• `0 <= nums[i] <= 1000`
• `0 <= sum(nums[i]) <= 1000`
• `-1000 <= target <= 1000`

SOLUTION:

``````class Solution:
def findways(self, nums: List[int], target: int, n, i) -> int:
ways = 0
if i >= n:
return ways
if (target, i) in self.cache:
return self.cache[(target, i)]
if i == n - 1:
if nums[i] == target:
ways += 1
if nums[i] == -target:
ways += 1
ways += self.findways(nums, target + nums[i], n, i + 1)
ways += self.findways(nums, target - nums[i], n, i + 1)
self.cache[(target, i)] = ways
return ways

def findTargetSumWays(self, nums: List[int], target: int) -> int:
self.cache = {}
return self.findways(nums, target, len(nums), 0)

# class Solution:
#     def isSubsetSum(self, arr, total, n):
#         if total == 0:
#             return True
#         if total != 0 and n == 0:
#             return False
#         if (n, total) in self.cache:
#             return self.cache[(n, total)]
#         if 2 * arr[n - 1] > total:
#             return self.isSubsetSum(arr, total, n - 1)
#         self.cache[(n, total)] = self.isSubsetSum(arr, total, n - 1) or self.isSubsetSum(arr, total - 2 * arr[n - 1], n - 1)
#         return self.cache[(n, total)]

#     def findTargetSumWays(self, nums: List[int], target: int) -> int:

# class Solution:
#     def findTargetSumWays(self, nums: List[int], target: int) -> int:
#         n = len(nums)
#         ctr = 0
#         paths = [(nums[0], 0)]
#         while len(paths) > 0:
#             val, i = paths.pop(0)
#             if val == target:
#                 ctr += 1
#             if i < n - 1:
#                 paths.append((val + nums[i + 1], i + 1))
#                 paths.append((val - nums[i + 1], i + 1))
#         return ctr

# class Solution:
#     def findTargetSumWays(self, nums: List[int], target: int) -> int:
#         n = len(nums)
#         ctr = 0
#         total = sum(nums)
#         k = (total + target) // 2
#         sums = [(num, i) for i, num in enumerate(nums)]
#         while len(sums) > 0:
#             curr, i = sums.pop(0)
#             if curr == k:
#                 ctr += 1
#             for j in range(i + 1, n):
#                 if curr + nums[j] <= k:
#                     sums.append((curr + nums[j], j))
#         return ctr
``````