# Target Sum

DFSDP

## # Solution

Let $n$ be the length of the array nums and $total$ be the total sum.

### # DFS

#### # Exponential Time (TLE)

The exponential runtime wouldn't pass on long nums.

# test case
nums = [38,21,23,36,1,36,18,3,37,27,29,29,35,47,16,0,2,42,46,6]
S = 14

1
2
3

Complexity

time: $O(2^n)$
space: $O(n)$

def findTargetSumWays(self, nums: List[int], S: int) -> int:
n = len(nums)
res = 0

def calculate(i, csum):
nonlocal res
if i == n:
if csum == S:
res += 1
else:
calculate(i+1, csum+nums[i])
calculate(i+1, csum-nums[i])

calculate(0, 0)
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#### #$O(n \cdot total)$ Time

Complexity

time: $O(n \cdot total)$
space: $O(n \cdot total)$

def findTargetSumWays(self, nums: List[int], S: int) -> int:
n = len(nums)
total = sum(nums)
res = 0
memo = [[-sys.maxsize for _ in range(total*2+1)] for _ in range(n)]

def calculate(i, csum):
if i == n:
if csum == S:
return 1
else:
return 0
else:
if memo[i][csum] > -sys.maxsize:
return memo[i][csum]

memo[i][csum] = calculate(i+1, csum+nums[i]) + calculate(i+1, csum-nums[i])
return memo[i][csum]

return calculate(0, 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

### # DP

dp[i][j] represents the number of ways summing previous $i$ elements to $j$.

The state transition is:
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

or:

dp[i][j + nums[i]] += dp[i - 1][j]
dp[i][j - nums[i]] += dp[i - 1][j]

As $j$ can reach $-total$ and $total$, the size of dp is $n \times (2 \cdot total + 1)$.

#### #$O(n \cdot total)$ Space

Complexity

time: $O(n \cdot total)$
space: $O(n \cdot total)$

def findTargetSumWays(self, nums: List[int], S: int) -> int:
n = len(nums)
total = sum(nums)
if not -total <= S <= total:
return 0
dp = [[0 for _ in range(total*2+1)] for _ in range(n)]

# base case
dp[0][total+nums[0]] = 1
dp[0][total-nums[0]] += 1

for i in range(1, n):
for j in range(total*2+1):
if j-nums[i]>=0 and dp[i-1][j-nums[i]]>0:
dp[i][j] += dp[i-1][j-nums[i]]
if j+nums[i]<=total*2 and dp[i-1][j+nums[i]]>0:
dp[i][j] += dp[i-1][j+nums[i]]

return dp[-1][total+S]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#### #$O(total)$ Space

Complexity

time: $O(n \cdot total)$
space: $O(total)$

def findTargetSumWays(self, nums: List[int], S: int) -> int:
n = len(nums)
total = sum(nums)
if not -total <= S <= total:
return 0
dp = [0 for _ in range(total*2+1)]

# base case
dp[total+nums[0]] = 1
dp[total-nums[0]] += 1

for i in range(1, n):
nxt = [0 for _ in range(total*2+1)]
for j in range(total*2+1):
if j-nums[i]>=0 and dp[j-nums[i]]>0:
nxt[j] += dp[j-nums[i]]
if j+nums[i]<=total*2 and dp[j+nums[i]]>0:
nxt[j] += dp[j+nums[i]]
dp = nxt

return dp[total+S]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Use another state transition and reduce the range of $j$ to traverse. Cannot use the previous relation b/c dp[:nums[i]] and dp[total*2+1-nums[i]:] would never be updated.

def findTargetSumWays(self, nums: List[int], S: int) -> int:
n = len(nums)
total = sum(nums)
if S > total:
return 0
dp = [0 for _ in range(total*2+1)]

# base case
dp[total+nums[0]] = 1
dp[total-nums[0]] += 1

for i in range(1, n):
nxt = [0 for _ in range(total*2+1)]
for j in range(nums[i], total*2+1-nums[i]):
nxt[j-nums[i]] += dp[j]
nxt[j+nums[i]] += dp[j]
dp = nxt

return dp[total+S]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19