LeetCode 494: Target Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 494: Target Sum?

In LeetCode 494: Target Sum, you’re given an integer array nums and a target integer target, and your task is to find the number of ways to assign either a + or - sign to each element so that the resulting sum equals target. For example, with nums = [1, 1, 1, 1, 1] and target = 3, you can assign signs like [+1, +1, +1, -1, -1] or [+1, +1, -1, +1, -1] (among others), totaling 5 ways. It’s like flipping coins with numbers, counting how many combinations land on your target sum.

Problem Statement

• Input: nums (List[int])—array of non-negative integers; target (int)—desired sum.
• Output: int—number of ways to assign + or - to reach target.
• Rules:
• Assign + or - to each element exactly once.
• Compute sum of signed elements.
• Count all combinations equaling target.

Constraints

• \( 0 \leq nums.length \leq 20 \).
• \( 0 \leq nums[i] \leq 1000 \).
• \( -1000 \leq target \leq 1000 \).

Examples to Get Us Started

• Input: nums = [1,1,1,1,1], target = 3
• Output: 5 (Ways: [+1,+1,+1,-1,-1], [+1,+1,-1,+1,-1], etc.).
• Input: nums = [1], target = 1
• Output: 1 (Only way: [+1]).
• Input: nums = [1,2,1], target = 0
• Output: 2 (Ways: [+1,-2,+1], [-1,+2,-1]).

Understanding the Problem: Conjuring the Sum

To solve LeetCode 494: Target Sum in Python, we need to count all ways to assign + or - to each element in nums so their signed sum equals target. A naive approach—trying all 2^n sign combinations—would be O(2^n), slow for n = 20 (over a million tries). The key? Transform it into a subset sum problem using dynamic programming, where we find subsets P (positive) and N (negative) such that P - N = target, optimizing to O(n * S) time (S = sum of nums). We’ll explore:

• Best Solution (Dynamic Programming with Subset Sum): O(n * S) time, O(S) space—fast and optimal.
• Alternative Solution (Brute Force Recursion): O(2^n) time, O(n) space—simple but slow.

Let’s dive into the DP solution—it’s the magician’s clever wand we need.

Best Solution: Dynamic Programming with Subset Sum

Why This Is the Best Solution

The dynamic programming with subset sum approach is the top pick because it’s O(n * S) time (n = array length, S = sum of nums) and O(S) space, efficiently counting ways to reach the target by converting the problem into finding how many ways a subset of nums can sum to a specific value derived from target and total sum. It uses a 1D DP array to track counts, avoiding exponential recursion. It’s like waving a wand to transform a sign-flipping puzzle into a familiar sum game—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Transform the problem:
• Let P = sum of positive elements, N = sum of negative elements.
• Total sum S = P + N.
• Target T = P - N.
• Solve: P - N = T, P + N = S → 2P = S + T → P = (S + T) / 2.
• Find ways to form subset summing to P.
• Step 2: Validate:
• S + T must be even, P must be non-negative and integer.
• Step 3: DP setup:
• \( dp[x] \) = ways to form sum x using elements up to i.
• Init: \( dp[0] = 1 \) (empty subset).
• For each num: update \( dp[x] += dp[x - num] \) for x ≥ num.
• Step 4: Return \( dp[P] \) if valid, else 0.
• Why It Works:
• Subset sum counts ways to achieve P, equivalent to target with signs.
• DP avoids recomputing combinations.

Step-by-Step Example

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

• S = 5, T = 3.
• P = (S + T) / 2 = (5 + 3) / 2 = 4 (even, valid).
• DP Init: \( dp[0] = 1 \), size = 5 (0 to 4).
• num = 1:
• \( dp[1] += dp[0] = 1 \), \( dp[2] += dp[1] = 1 \), …, \( dp[4] += dp[3] = 1 \).
• \( dp = [1, 1, 1, 1, 1] \).
• num = 1:
• \( dp[1] += dp[0] = 2 \), \( dp[2] += dp[1] = 3 \), …, \( dp[4] += dp[3] = 5 \).
• \( dp = [1, 2, 3, 4, 5] \).
• Repeat 3 more times: Final \( dp[4] = 5 \) (ways to sum to 4 with five 1s).
• Result: 5.

Example: nums = [1,2,1], target = 0

• S = 4, T = 0, P = 2.
• DP: \( dp[0] = 1 \), after nums: \( dp[2] = 2 \) ([1,1], [-1,+2,-1]).
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # Step 1: Compute total sum and target subset sum
        total = sum(nums)
        if total < abs(target) or (total + target) % 2 != 0:
            return 0
        subset_sum = (total + target) // 2

        # Step 2: Validate subset_sum
        if subset_sum < 0:
            return 0

        # Step 3: DP setup
        dp = [0] * (subset_sum + 1)
        dp[0] = 1  # Base case: empty subset

        # Process each number
        for num in nums:
            for j in range(subset_sum, num - 1, -1):
                dp[j] += dp[j - num]

        # Step 4: Return ways to form subset_sum
        return dp[subset_sum]

• Line 4-7: Compute total, check if (S + T) even and target reachable.
• Line 8-10: Compute P, validate non-negative.
• Line 13-14: Init DP array, \( dp[0] = 1 \).
• Line 17-19: For each num, update \( dp[j] \) from right to left.
• Line 22: Return \( dp[P] \).
• Time Complexity: O(n * S)—n elements, S = subset sum size.
• Space Complexity: O(S)—DP array.

It’s like a sum-conjuring wand!

Alternative Solution: Brute Force Recursion

Why an Alternative Approach?

The brute force recursion—O(2^n) time, O(n) space—tries all 2^n sign combinations by recursively assigning + or - to each element, counting when the sum matches target. It’s slow but intuitive, like flipping every coin to see which sums land on target. Good for small arrays or learning!

How It Works

• Step 1: Recurse with index, current sum:
• Base: if index = len(nums), check if sum = target.
• Step 2: For each index:
• Try +num, recurse.
• Try -num, recurse.
• Step 3: Sum results from recursive calls.
• Step 4: Start recursion, return count.

Step-by-Step Example

Example: nums = [1,1], target = 0

• dfs(0, 0):
• \( dfs(1, 1) \): \( dfs(2, 2) = 0 \), \( dfs(2, 0) = 1 \).
• \( dfs(1, -1) \): \( dfs(2, 0) = 1 \), \( dfs(2, -2) = 0 \).
• Result: 1 + 1 = 2.

Code for Brute Force

Copy codeclass Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def dfs(index: int, curr_sum: int) -> int:
            if index == len(nums):
                return 1 if curr_sum == target else 0
            # Try + and - for current number
            return dfs(index + 1, curr_sum + nums[index]) + dfs(index + 1, curr_sum - nums[index])

        return dfs(0, 0)

• Line 3-8: Recurse, count matches at end.
• Time Complexity: O(2^n)—each element has 2 choices.
• Space Complexity: O(n)—recursion stack.

It’s a slow sign flipper!

Comparing the Two Solutions

• DP with Subset Sum (Best):
• Pros: O(n * S), fast, scalable.
• Cons: O(S) space.
• Brute Force (Alternative):
• Pros: O(2^n), simple.
• Cons: Slow for large n.

DP wins for efficiency.

Edge Cases and Examples

• Input: [], 0 → 1.
• Input: [1], 2 → 0.
• Input: [0,0], 0 → 4.

DP handles all perfectly.

Complexity Recap

• DP: Time O(n * S), Space O(S).
• Brute Force: Time O(2^n), Space O(n).

DP’s the champ.

Key Takeaways

• DP: Transform to subset sum.
• Brute Force: Try all signs.
• Python Tip: DP optimizes—see [Python Basics](/python/basics).

Final Thoughts: Cast That Sum

LeetCode 494: Target Sum in Python is a sum-conjuring math adventure. DP with subset sum is your fast wand, while brute force is a slow spell. Want more sum challenges? Try LeetCode 416: Partition Equal Subset Sum or LeetCode 518: Coin Change II. Ready to hit some targets? Head to Solve LeetCode 494 on LeetCode and conjure it today—your coding skills are magic-ready!