MediumNo. 0494

Target Sum — LeetCode 494 Python Solution

Topics
Array, Dynamic Programming, Backtracking
On a study list
NeetCode 150
Reading time
3 min

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

PythonSolution
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

Time
O(m × n)
Space · auxiliary
O(m × n)

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

Frequently asked questions

How hard is LeetCode 494. Target Sum?

LeetCode 494. Target Sum is rated Medium on LeetCode.

What is the time complexity of LeetCode 494. Target Sum?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 494. Target Sum?

The Python solution on this page uses O(m × n) auxiliary space.

What topics does LeetCode 494. Target Sum cover?

LeetCode 494. Target Sum is tagged Array, Dynamic Programming and Backtracking on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.