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.
- code dfs
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def dfs(nums_left, path_sum, memo):
key = (path_sum, tuple(nums_left))
if key in memo: return memo[key]
if not nums_left: return 1 if target == path_sum else 0
memo[key] = dfs(nums_left[1:], path_sum + nums_left[0], memo) + dfs(nums_left[1:], path_sum - nums_left[0], memo)
return memo[key]
return dfs(nums, 0, {})
- code best, get(key, default) if key doesn’t exist.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
counter = {0: 1}
for num in nums:
tmp = {}
for saved in counter:
cur = saved + num
tmp[cur] = tmp.get(cur, 0) + counter[saved]
cur = saved - num
tmp[cur] = tmp.get(cur, 0) + counter[saved]
counter = tmp
return counter.get(target, 0)
- code TLE
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def dfs(nums_left, path_sum):
if nums_left == []:
if target == path_sum:
nonlocal res
res += 1
return
for flag in [1, -1]:
cur = nums_left.pop()
dfs(nums_left, path_sum + cur * flag)
nums_left.append(cur)
res = 0
dfs(nums, 0)
return res
- code time limit exceeded
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# q = collections.deque([0])
q = [0]
while q and nums:
num = nums.pop()
next = []
for i in range(len(q)):
# cur = q.popleft()
# q.append(cur - num)
# q.append(cur + num)
next.append(q[i] + num)
next.append(q[i] - num)
q = next
return next.count(target)
# dict(collections.Counter(q))[target]
- code
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
## RC ##
## APPROACH : DP ##
## INTUITION : THINK LIKE SUBSET SUM PROBLEM (tushor roy DP solution) Leetcode 416. Partition equal subset sum ##
# but here 1. our target can range from -totalSum to +totalSum
# 2. and we dont include True directly from above sequence, coz it is not subsequence we are looking for. so here consider if and only if previous value exists
# [1,1,1,1,1]
# 3
# [
# [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
# [0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0],
# [0, 0, 1, 0, 3, 0, 3, 0, 1, 0, 0],
# [0, 1, 0, 4, 0, 6, 0, 4, 0, 1, 0],
# [1, 0, 5, 0, 10, 0, 10, 0, 5, 0, 1]
# ]
## TIME COMPLEXITY : O(N^2) ##
## SPACE COMPLEXITY : O(N^2) ##
totalSum = sum(nums)
if(target not in range(-1 * totalSum, totalSum + 1) ): return 0
dp = [ [ 0 for j in range( totalSum*2 + 1 ) ] for i in range(len(nums))]
## BASE CASE ## FIRST ROW ##
dp[0][totalSum + nums[0]] += 1
dp[0][totalSum - nums[0]] += 1
for i in range(1, len(nums)):
for j in range( totalSum*2 + 1 ):
if( j - nums[i] >= 0 and dp[i-1][j-nums[i]] > 0 ): # left side
dp[i][j] += dp[i-1][j-nums[i]]
if( j + nums[i] <= totalSum*2 and dp[i-1][j+nums[i]] > 0 ): # right side
dp[i][j] += dp[i-1][j+nums[i]]
return dp[-1][totalSum + target]