494. Target sum

494_solution1_tab.c

#include <stdlib.h>

int findTargetSumWays(int *nums, int numsSize, int target) {
  int n = numsSize;
  int tot = 0;
  for (int i = 0; i < n; i++)
    tot += nums[i];
  if (abs(target) > tot)
    return 0;

  int w = 2 * tot + 1;
  int *dp = calloc((n + 1) * w, sizeof(int)); // dp[i * w + (s + tot)]
  dp[0 * w + (0 + tot)] = 1;                  // 0 numbers used, sum 0

  for (int i = 1; i <= n; i++) {
    int x = nums[i - 1];
    for (int s = -tot; s <= tot; s++) {
      int ways = 0;
      if (s - x >= -tot)
        ways += dp[(i - 1) * w + (s - x + tot)]; // added x
      if (s + x <= tot)
        ways += dp[(i - 1) * w + (s + x + tot)]; // subtracted x
      dp[i * w + (s + tot)] = ways;
    }
  }
  int res = dp[n * w + (target + tot)];
  free(dp);
  return res;
}

494_solution2_memo.c

#include <stdlib.h>

static int *nums_, n_, tot_, target_, w_;
static int *dp; // dp[i * w_ + (sum + tot_)], -1 = not computed

// Ways to reach target using nums[i..], given the running sum so far
static int f(int i, int sum) {
  if (i == n_)
    return sum == target_ ? 1 : 0;
  if (dp[i * w_ + (sum + tot_)] != -1)
    return dp[i * w_ + (sum + tot_)];

  int add = f(i + 1, sum + nums_[i]); // +nums[i]
  int sub = f(i + 1, sum - nums_[i]); // -nums[i]
  return dp[i * w_ + (sum + tot_)] = add + sub;
}

int findTargetSumWays(int *nums, int numsSize, int target) {
  int tot = 0;
  for (int i = 0; i < numsSize; i++)
    tot += nums[i];
  if (abs(target) > tot)
    return 0;

  nums_ = nums, n_ = numsSize, tot_ = tot, target_ = target, w_ = 2 * tot + 1;
  dp = malloc(n_ * w_ * sizeof(int));
  for (int k = 0; k < n_ * w_; k++)
    dp[k] = -1;
  int res = f(0, 0);
  free(dp);
  return res;
}

494_solution1_tab.cpp

#include <cstdlib>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
  int findTargetSumWays(vector<int> &nums, int target) {
    int n = nums.size();
    int tot = accumulate(nums.begin(), nums.end(), 0);
    if (abs(target) > tot)
      return 0;

    vector<vector<int>> dp(n + 1, vector<int>(2 * tot + 1, 0));
    dp[0][0 + tot] = 1; // 0 numbers used, sum 0

    for (int i = 1; i <= n; i++) {
      int x = nums[i - 1];
      for (int s = -tot; s <= tot; s++) {
        int ways = 0;
        if (s - x >= -tot)
          ways += dp[i - 1][s - x + tot]; // added x
        if (s + x <= tot)
          ways += dp[i - 1][s + x + tot]; // subtracted x
        dp[i][s + tot] = ways;
      }
    }
    return dp[n][target + tot];
  }
};

494_solution2_memo.cpp

#include <cstdlib>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
  int tot, target;
  vector<vector<int>> dp; // dp[i][sum + tot], -1 = not computed

  // Ways to reach target using nums[i..], given the running sum so far
  int f(int i, int sum, vector<int> &nums) {
    if (i == (int)nums.size())
      return sum == target ? 1 : 0;
    if (dp[i][sum + tot] != -1)
      return dp[i][sum + tot];

    int add = f(i + 1, sum + nums[i], nums); // +nums[i]
    int sub = f(i + 1, sum - nums[i], nums); // -nums[i]
    return dp[i][sum + tot] = add + sub;
  }

public:
  int findTargetSumWays(vector<int> &nums, int target) {
    int n = nums.size();
    tot = accumulate(nums.begin(), nums.end(), 0);
    if (abs(target) > tot)
      return 0;

    this->target = target;
    dp.assign(n, vector<int>(2 * tot + 1, -1));
    return f(0, 0, nums);
  }
};

494_solution1_tab.go

package dp

func findTargetSumWays(nums []int, target int) int {
    n := len(nums)
    tot := 0
    for _, x := range nums {
        tot += x
    }
    if target > tot || target < -tot {
        return 0
    }

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, 2*tot+1)
    }
    dp[0][0+tot] = 1 // 0 numbers used, sum 0

    for i := 1; i <= n; i++ {
        x := nums[i-1]
        for s := -tot; s <= tot; s++ {
            ways := 0
            if s-x >= -tot {
                ways += dp[i-1][s-x+tot] // added x
            }
            if s+x <= tot {
                ways += dp[i-1][s+x+tot] // subtracted x
            }
            dp[i][s+tot] = ways
        }
    }
    return dp[n][target+tot]
}

494_solution2_memo.go

package dp

func findTargetSumWays(nums []int, target int) int {
    n := len(nums)
    tot := 0
    for _, x := range nums {
        tot += x
    }
    if target > tot || target < -tot {
        return 0
    }

    dp := make([][]int, n) // dp[i][sum+tot], -1 = not computed
    for i := range dp {
        dp[i] = make([]int, 2*tot+1)
        for s := range dp[i] {
            dp[i][s] = -1
        }
    }

    // f returns the ways to reach target using nums[i..], given the running sum so far
    var f func(i, sum int) int
    f = func(i, sum int) int {
        if i == n {
            if sum == target {
                return 1
            }
            return 0
        }
        if dp[i][sum+tot] != -1 {
            return dp[i][sum+tot]
        }

        add := f(i+1, sum+nums[i]) // +nums[i]
        sub := f(i+1, sum-nums[i]) // -nums[i]
        dp[i][sum+tot] = add + sub
        return dp[i][sum+tot]
    }

    return f(0, 0)
}

494_solution1_tab.java

import java.util.Arrays;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int tot = Arrays.stream(nums).sum();
        if (Math.abs(target) > tot)
            return 0;

        int[][] dp = new int[n + 1][2 * tot + 1];
        dp[0][0 + tot] = 1; // 0 numbers used, sum 0

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = -tot; s <= tot; s++) {
                int ways = 0;
                if (s - x >= -tot)
                    ways += dp[i - 1][s - x + tot]; // added x
                if (s + x <= tot)
                    ways += dp[i - 1][s + x + tot]; // subtracted x
                dp[i][s + tot] = ways;
            }
        }
        return dp[n][target + tot];
    }
}

494_solution2_memo.java

import java.util.Arrays;

class Solution {
    private int tot, target;
    private int[][] dp; // dp[i][sum + tot], -1 = not computed

    // Ways to reach target using nums[i..], given the running sum so far
    private int f(int i, int sum, int[] nums) {
        if (i == nums.length)
            return sum == target ? 1 : 0;
        if (dp[i][sum + tot] != -1)
            return dp[i][sum + tot];

        int add = f(i + 1, sum + nums[i], nums); // +nums[i]
        int sub = f(i + 1, sum - nums[i], nums); // -nums[i]
        return dp[i][sum + tot] = add + sub;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        tot = Arrays.stream(nums).sum();
        if (Math.abs(target) > tot)
            return 0;

        this.target = target;
        dp = new int[n][2 * tot + 1];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return f(0, 0, nums);
    }
}

494_solution1_tab.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  const n = nums.length;
  const tot = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > tot) return 0;

  const dp = Array.from({ length: n + 1 }, () => new Array(2 * tot + 1).fill(0));
  dp[0][0 + tot] = 1; // 0 numbers used, sum 0

  for (let i = 1; i <= n; i++) {
    const x = nums[i - 1];
    for (let s = -tot; s <= tot; s++) {
      let ways = 0;
      if (s - x >= -tot) ways += dp[i - 1][s - x + tot]; // added x
      if (s + x <= tot) ways += dp[i - 1][s + x + tot]; // subtracted x
      dp[i][s + tot] = ways;
    }
  }
  return dp[n][target + tot];
};

494_solution2_memo.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  const n = nums.length;
  const tot = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > tot) return 0;

  // dp[i][sum + tot], -1 = not computed
  const dp = Array.from({ length: n }, () => new Array(2 * tot + 1).fill(-1));

  // Ways to reach target using nums[i..], given the running sum so far
  const f = (i, sum) => {
    if (i === n) return sum === target ? 1 : 0;
    if (dp[i][sum + tot] !== -1) return dp[i][sum + tot];

    const add = f(i + 1, sum + nums[i]); // +nums[i]
    const sub = f(i + 1, sum - nums[i]); // -nums[i]
    return (dp[i][sum + tot] = add + sub);
  };

  return f(0, 0);
};

494_solution1_tab.py

from typing import List


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        tot = sum(nums)
        if abs(target) > tot:
            return 0

        dp = [[0] * (2 * tot + 1) for _ in range(n + 1)]
        dp[0][0 + tot] = 1  # 0 numbers used, sum 0

        for i in range(1, n + 1):
            x = nums[i - 1]
            for s in range(-tot, tot + 1):
                ways = 0
                if s - x >= -tot:
                    ways += dp[i - 1][s - x + tot]  # added x
                if s + x <= tot:
                    ways += dp[i - 1][s + x + tot]  # subtracted x
                dp[i][s + tot] = ways
        return dp[n][target + tot]

494_solution2_memo.py

from typing import List


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        tot = sum(nums)
        if abs(target) > tot:
            return 0

        dp = [[-1] * (2 * tot + 1) for _ in range(n)]  # dp[i][sum + tot], -1 = not computed

        def f(i: int, total: int) -> int:
            """Ways to reach target using nums[i:], given the running sum so far."""
            if i == n:
                return 1 if total == target else 0
            if dp[i][total + tot] != -1:
                return dp[i][total + tot]

            add = f(i + 1, total + nums[i])  # +nums[i]
            sub = f(i + 1, total - nums[i])  # -nums[i]
            dp[i][total + tot] = add + sub
            return dp[i][total + tot]

        return f(0, 0)

494_solution1_tab.rs

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let tot: i32 = nums.iter().sum();
        if target.abs() > tot {
            return 0;
        }

        let idx = |s: i32| (s + tot) as usize; // shift sums into 0..=2*tot
        let mut dp = vec![vec![0; 2 * tot as usize + 1]; n + 1];
        dp[0][idx(0)] = 1; // 0 numbers used, sum 0

        for i in 1..=n {
            let x = nums[i - 1];
            for s in -tot..=tot {
                let mut ways = 0;
                if s - x >= -tot {
                    ways += dp[i - 1][idx(s - x)]; // added x
                }
                if s + x <= tot {
                    ways += dp[i - 1][idx(s + x)]; // subtracted x
                }
                dp[i][idx(s)] = ways;
            }
        }
        dp[n][idx(target)]
    }
}

494_solution2_memo.rs

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        let tot: i32 = nums.iter().sum();
        if target.abs() > tot {
            return 0;
        }

        // dp[i][sum + tot], -1 = not computed
        let mut dp = vec![vec![-1; 2 * tot as usize + 1]; nums.len()];
        Self::f(0, 0, &nums, target, tot, &mut dp)
    }

    // Ways to reach target using nums[i..], given the running sum so far
    fn f(i: usize, sum: i32, nums: &[i32], target: i32, tot: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
        if i == nums.len() {
            return if sum == target { 1 } else { 0 };
        }
        let k = (sum + tot) as usize;
        if dp[i][k] != -1 {
            return dp[i][k];
        }

        let add = Self::f(i + 1, sum + nums[i], nums, target, tot, dp); // +nums[i]
        let sub = Self::f(i + 1, sum - nums[i], nums, target, tot, dp); // -nums[i]
        dp[i][k] = add + sub;
        dp[i][k]
    }
}