#494

Target Sum

medium· 2-D DPruns: 0

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of '+' or '-' before each integer and then concatenating them. Return the number of different expressions you can build that evaluate to target.

wpm 0acc 100%time 0:000 / 497

class Solution:
    def findTargetSumWays(
        self, nums: list[int], target: int
    ) -> int:
        memo = {}

        def dp(i: int, total: int) -> int:
            if i == len(nums):
                return 1 if total == target else 0
            if (i, total) in memo:
                return memo[(i, total)]
            memo[(i, total)] = dp(i + 1, total + nums[i]) + dp(
                i + 1, total - nums[i]
            )
            return memo[(i, total)]

        return dp(0, 0)

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.