Target sum problem

Problem Statement

Given:

• An array of integers nums[] (can include positive integers),
• A target integer S,

You can assign either a + or - sign to each element in nums.
Your task is to find how many ways to assign signs such that the sum equals S.

How It’s Related

• We want to partition the array into two subsets:
• S1 with elements assigned a + sign
• S2 with elements assigned a - sign
• The problem boils down to:

sum(S1) - sum(S2) = target (S)
sum(S1) + sum(S2) = total_sum

Adding:

2 * sum(S1) = target + total_sum
=> sum(S1) = (target + total_sum) / 2

So this problem reduces to counting subsets with sum = (target + total_sum)/2 (if this value is an integer and non-negative).

Important

• If (target + total_sum) is odd or negative → return 0
• The array elements are assumed to be non-negative

Example:

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

Output: 5

Ways:
+1 +1 +1 -1 -1 = 1
+1 +1 -1 +1 -1 = 1
+1 -1 +1 +1 -1 = 1
-1 +1 +1 +1 -1 = 1
+1 +1 -1 -1 +1 = 1

Python:

def find_target_sum_ways(nums, target):
    total_sum = sum(nums)
    
    # Check if (target +…