Target Sum — LeetCode 494 Python Solution

The problem

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

Example

Input

nums = [1,1,1,1,1], target = 3

Output

5

Explanation

There are 5 ways to assign symbols to make the sum of nums be target 3.

Python solution

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target or (s - target) % 2:
            return 0
        m, n = len(nums), (s - target) // 2
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i - 1][j - x]
        return f[m][n]

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 494. Target Sum is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems