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'+'before2and a'-'before1and 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
Top comments (0)