A few lines of JavaScript using DP/recursion/memoization


  • 0
    var findTargetSumWays = function(nums, S, sum = 0, i = 0, memo = new Map()) {
        let key = sum + ',' + i;
        if (memo.has(key)) return memo.get(key);
        if (i === nums.length) return +(sum === S);
        memo.set(key, findTargetSumWays(nums, S, sum + nums[i], i + 1, memo) + findTargetSumWays(nums, S, sum - nums[i], i + 1, memo));
        return memo.get(key);
    };
    

    Picture a tree in which each leaf node counts as one way if its path sum matches our target, and each parent counts the ways of its children. Nodes on the same level have identical ways when their path sums are equal, so we can memoize and share the ways of level i nodes that have sum path sums.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.