Skip to main content

494. Target Sum

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

Python​

Backtrack (Timelimit Exceed)​

  • Time: O(N**2)
  • Space: O(1)
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        count = 0

        def backtrack(i, remain):
            nonlocal count
            if i == len(nums):
                if remain == 0:
                    count += 1
                return

            backtrack(i+1, remain+nums[i])  # Pick -
            backtrack(i+1, remain-nums[i])  # Pick +

        backtrack(0, target)

        return count

Top-Down DP​

from functools import cache


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @cache
        def dp(i, remain):
            if i == len(nums):
                if remain == 0:
                    return 1
                return 0
            return dp(i+1, remain+nums[i]) + dp(i+1, remain-nums[i])

        return dp(0, target)

Javascript​

var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((acc, cur) => acc + cur);
    const dp = [...new Array(nums.length)].map(() => new Array(sum * 2 + 1).fill(0));
    // add 1 or -1 from total (5)
    dp[0][nums[0] + sum] = 1;
    dp[0][-nums[0] + sum] += 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = -sum; j <= sum; j++) {
            if (dp[i - 1][j + sum] > 0) {
                dp[i][j + sum + nums[i]] += dp[i - 1][j + sum];
                dp[i][j + sum - nums[i]] += dp[i - 1][j + sum];
            }
        }
    }
    // console.log(dp)
    return dp[nums.length - 1][target + sum] || 0;
};


/**
 *   -5 -4 -3 -2 -1 0  1 2 3 4 5
 * 0              1 0  1
 * 1           1  0 2  0 1
 * 2        1  0  3 0  3 0 1
 * 3     1  0  4  0 6  0 4 0 1
 * 4  1  0  5  0 10 0 10 4 5 0 1
 */