# 494. Target Sum

## Approach 1: 2D DP

• Time: $O(nk)$, where $k = (\Sigma \texttt{nums[i]} + S) / 2$
• Space: $O(nk)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int findTargetSumWays(vector& nums, int target) { const int sum = accumulate(begin(nums), end(nums), 0); if (sum < abs(target) || (sum + target) & 1) return 0; return knapsack(nums, (sum + target) / 2); } private: int knapsack(const vector& nums, int target) { const int n = nums.size(); // dp[i][j] := # of ways to sum to j by nums[0..i) vector> dp(n + 1, vector(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]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int findTargetSumWays(int[] nums, int target) { final int sum = Arrays.stream(nums).sum(); if (sum < Math.abs(target) || (sum + target) % 2 == 1) return 0; return knapsack(nums, (sum + target) / 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]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: summ = sum(nums) if summ < abs(target) or (summ + target) & 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 + target) // 2) 

## Approach 2: 1D DP

• Time: $O(nk)$
• Space: $O(k)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int findTargetSumWays(vector& nums, int target) { const int sum = accumulate(begin(nums), end(nums), 0); if (sum < abs(target) || (sum + target) & 1) return 0; return knapsack(nums, (sum + target) / 2); } private: int knapsack(const vector& nums, int target) { // dp[i] := # of ways to sum to i by nums so far vector 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]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int findTargetSumWays(int[] nums, int target) { final int sum = Arrays.stream(nums).sum(); if (sum < Math.abs(target) || (sum + target) % 2 == 1) return 0; return knapsack(nums, (sum + target) / 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]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: summ = sum(nums) if summ < abs(target) or (summ + target) & 1: return 0 def knapsack(nums: List[int], target: int) -> int: # dp[i] := # of ways to sum to i by nums so far dp = [0] * (target + 1) dp[0] = 1 for num in nums: for i in range(target, num - 1, -1): dp[i] += dp[i - num] return dp[target] return knapsack(nums, (summ + target) // 2)