## Approach 1: 2D DP

• Time:O(nk), where k = (\Sigma \texttt{nums[i]} + S) / 2
• Space:O(nk)

## C++

``````class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
const int sum = accumulate(begin(nums), end(nums), 0);
if (sum < S || (sum + S) & 1)
return 0;

return knapsack(nums, (sum + S) / 2);
}

private:
int knapsack(const vector<int>& nums, int target) {
const int n = nums.size();
// dp[i][j] := # of ways to sum to j by nums[0..i)
vector<vector<int>> dp(n + 1, vector<int>(target + 1));
dp[0][0] = 1;

for (int i = 1; i <= n; ++i) {
const int num = nums[i - 1];
for (int j = 0; j <= target; ++j) {
if (j < num)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
}
}

return dp[n][target];
}
};
``````

## JAVA

``````class Solution {
public int findTargetSumWays(int[] nums, int S) {
final int sum = Arrays.stream(nums).sum();
if (sum < S || (sum + S) % 2 == 1)
return 0;

return knapsack(nums, (sum + S) / 2);
}

private int knapsack(int[] nums, int target) {
final int n = nums.length;
// dp[i][j] := # of ways to sum to j by nums[0..i)
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;

for (int i = 1; i <= n; ++i) {
final int num = nums[i - 1];
for (int j = 0; j <= target; ++j) {
if (j < num)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
}
}

return dp[n][target];
}
}
``````

## Python

``````class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
summ = sum(nums)
if summ < S or (summ + S) & 1:
return 0

def knapsack(target: int) -> int:
# dp[i] := # of ways to sum to i by nums so far
dp = [1] + [0] * summ

for num in nums:
for j in range(summ, num - 1, -1):
dp[j] += dp[j - num]

return dp[target]

return knapsack((summ + S) // 2)
``````

• Time:O(nk)
• Space:O(k)

## C++

``````class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
const int sum = accumulate(begin(nums), end(nums), 0);
if (sum < S || (sum + S) & 1)
return 0;

return knapsack(nums, (sum + S) / 2);
}

private:
int knapsack(const vector<int>& nums, int target) {
// dp[i] := # of ways to sum to i by nums so far
vector<int> dp(target + 1);
dp[0] = 1;

for (const int num : nums)
for (int i = target; i >= num; --i)
dp[i] += dp[i - num];

return dp[target];
}
};
``````

## JAVA

``````class Solution {
public int findTargetSumWays(int[] nums, int S) {
final int sum = Arrays.stream(nums).sum();
if (sum < S || (sum + S) % 2 == 1)
return 0;

return knapsack(nums, (sum + S) / 2);
}

private int knapsack(int[] nums, int target) {
// dp[i] := # of ways to sum to i by nums so far
int[] dp = new int[target + 1];
dp[0] = 1;

for (final int num : nums)
for (int i = target; i >= num; --i)
dp[i] += dp[i - num];

return dp[target];
}
}
``````