Target Sum
Tags: leetcode, dsa, theabbie
Published: 2022-06-05 03:30:37

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