Target Sum

DFSDP
https://leetcode.com/problems/target-sum

# Solution

Let nn be the length of the array nums and totaltotal be the total sum.

# DFS Recursion

Let n be the sum of negative numbers, p the sum of positive numbers, and s be the sum of all numbers in nums.

p=capp = cap in 0/1 knapsack:
dfs(i, p) = dfs(i-1, p) + dfs(i-1, p-nums[i])

def findTargetSumWays(self, nums: List[int], target: int) -> int:
    # n + p = s
    # n = s - p
    # p - n = t
    # p - (s - p) = t
    # search for p: p = (t + s) / 2
    sm = sum(nums)
    if sm < target or (sm + target) % 2 == 1:
        return 0
    p = (sm + target) // 2

    @cache
    def dfs(i, p):
        if i < 0:
            return 1 if p == 0 else 0
        
        if p < nums[i]:
            res = dfs(i-1, p)
        else:
            res = dfs(i-1, p) + dfs(i-1, p-nums[i])
        return res
    return dfs(len(nums)-1, p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# DP Iteration

# O(n⋅p)O(n \cdot p) space

def findTargetSumWays(self, nums: List[int], target: int) -> int:
    n = len(nums)
    dp = [[0 for _ in range(p+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(p+1):
            if j < nums[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]]
    return d[n][p]
1
2
3
4
5
6
7
8
9
10
11

# O(2⋅p)O(2 \cdot p) Space

def findTargetSumWays(self, nums: List[int], target: int) -> int:
    n = len(nums)
    dp = [[0 for _ in range(p+1)] for _ in range(2)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(p+1):
            if j < nums[i]:
                dp[(i+1)%2][j] = dp[i%2][j]
            else:
                dp[(i+1)%2][j] = dp[i%2][j] + dp[i%2][j-nums[i]]
    return dp[n%2][p]
1
2
3
4
5
6
7
8
9
10
11

# O(p)O(p) Space

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int temp = sum + target;
    if (temp < 0) return 0;
    if (temp % 2 == 1) return false;
    int pos_sum = (sum + target) / 2;
    vector<int> dp(pos_sum+1, 0);
    dp[0] = 1;
    for (int num : nums) {
        for (int i = pos_sum; i >= num; i--) { // reverse order
            dp[i] += dp[i-num];
        }
    }
    return dp[pos_sum];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Tenth Line