Problem of The Day: Target Sum

Problem Statement

Intuition

The problem requires finding the number of ways to assign + and - signs to elements in the array such that their sum equals a given target. At first glance, this can be visualized as a tree of decisions, where each node represents a choice: adding or subtracting the current number.

Approach

The solution uses a Depth First Search (DFS) approach with memoization. Here’s how it works:

1. Recursive Decision Tree:

   • For each number in the array, you can either add it or subtract it from the current sum.
   • This creates a binary tree where each node represents a partial sum.

2. Base Case:

   • When all numbers have been processed (i.e., the index equals the length of the array), check if the current sum equals the target. If it does, this is a valid solution.

3. Memoization:

   • To optimize the solution and avoid recalculating results for the same state, store the results of previously computed states in a dictionary (memo).
   • A state is uniquely identified by the index and the curr_sum.

4. Recursive Calculation:

   • At each recursive call, calculate the number of ways for both adding and subtracting the current number.
   • Sum these results and store them in the memo for reuse.

Complexity

• Time complexity: \(O(n \cdot S)\)
  where (n) is the number of elements in the array, and (S) is the range of possible sums. Memoization ensures each state is computed only once.

• Space complexity: \(O(n \cdot S)\)
  for the memoization dictionary and the recursion stack.

Code

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def dfs(index, curr_sum, memo):
            if index == len(nums):
                return curr_sum == target
            if (index, curr_sum) in memo:
                return memo[(index, curr_sum)]
            positive = dfs(index + 1, curr_sum + nums[index], memo)
            negative = dfs(index + 1, curr_sum - nums[index], memo)
            memo[(index, curr_sum)] = positive + negative
            return memo[(index, curr_sum)]

        memo = defaultdict(int)
        return dfs(0, 0, memo)

Editorial

Approach 2: Recursion with Memoization

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.total_sum = sum(nums)
        memo = [
            [float("-inf")] * (2 * self.total_sum + 1) for _ in range(len(nums))
        ]
        return self.calculate_ways(nums, 0, 0, target, memo)

    def calculate_ways(
        self,
        nums: List[int],
        current_index: int,
        current_sum: int,
        target: int,
        memo: List[List[int]],
    ) -> int:
        if current_index == len(nums):
            # Check if the current sum matches the target
            return 1 if current_sum == target else 0
        else:
            # Check if the result is already computed
            if memo[current_index][current_sum + self.total_sum] != float(
                "-inf"
            ):
                return memo[current_index][current_sum + self.total_sum]

            # Calculate ways by adding the current number
            add = self.calculate_ways(
                nums,
                current_index + 1,
                current_sum + nums[current_index],
                target,
                memo,
            )

            # Calculate ways by subtracting the current number
            subtract = self.calculate_ways(
                nums,
                current_index + 1,
                current_sum - nums[current_index],
                target,
                memo,
            )

            # Store the result in memoization table
            memo[current_index][current_sum + self.total_sum] = add + subtract

            return memo[current_index][current_sum + self.total_sum]

Approach 3: 2D Dynamic Programming

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        dp = [[0] * (2 * total_sum + 1) for _ in range(len(nums))]

        # Initialize the first row of the DP table
        dp[0][nums[0] + total_sum] = 1
        dp[0][-nums[0] + total_sum] += 1

        # Fill the DP table
        for index in range(1, len(nums)):
            for sum_val in range(-total_sum, total_sum + 1):
                if dp[index - 1][sum_val + total_sum] > 0:
                    dp[index][sum_val + nums[index] + total_sum] += dp[
                        index - 1
                    ][sum_val + total_sum]
                    dp[index][sum_val - nums[index] + total_sum] += dp[
                        index - 1
                    ][sum_val + total_sum]

        # Return the result if the target is within the valid range
        return (
            0
            if abs(target) > total_sum
            else dp[len(nums) - 1][target + total_sum]
        )

Approach 4: Space Optimized

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        dp = [0] * (2 * total_sum + 1)

        # Initialize the first row of the DP table
        dp[nums[0] + total_sum] = 1  # Adding nums[0]
        dp[-nums[0] + total_sum] += 1  # Subtracting nums[0]

        # Fill the DP table
        for index in range(1, len(nums)):
            next_dp = [0] * (2 * total_sum + 1)
            for sum_val in range(-total_sum, total_sum + 1):
                if dp[sum_val + total_sum] > 0:
                    next_dp[sum_val + nums[index] + total_sum] += dp[
                        sum_val + total_sum
                    ]
                    next_dp[sum_val - nums[index] + total_sum] += dp[
                        sum_val + total_sum
                    ]
            dp = next_dp

        # Return the result if the target is within the valid range
        return 0 if abs(target) > total_sum else dp[target + total_sum]