Target Sum is one of the most important Knapsack Pattern interview questions.

You are given:

nums[]
target 

Goal:

Assign '+' or '-' signs to each number so that the final expression equals the target value. 

Find:

Total number of possible ways. 

Example

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

Output:

5 

Explanation:

-1 + 1 + 1 + 1 + 1 = 3
1 - 1 + 1 + 1 + 1 = 3
1 + 1 - 1 + 1 + 1 = 3
1 + 1 + 1 - 1 + 1 = 3
1 + 1 + 1 + 1 - 1 = 3 

Key Observation

Let:

s1 = positive numberss2 = negative numbers

Then:

s1 - s2 = target
s1 + s2 = totalSum 

Adding both equations:

2 × s1 = target + totalSum 

Therefore:

s1 = (target + totalSum) / 2

Now the problem becomes:

Count subsets whose sum equals s1. 

Approach 1 : Memoization

Explanation

For every number:

Pick or Not Pick 

Store answers and reuse calculations.

Approach 2 : Tabulation

Explanation

State:

dp[i][sum] = Number of ways to make sum using first i elements

Transition:

dp[i][sum] = pick + notPick

Meaning:

Ways including current number + Ways excluding current number 

Dry Run

Input:

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

Total Sum:

5 

Required Sum:

(5 + 3) / 2 = 4 

Count subsets with sum 4:

5 ways 

Answer:

5 

Approach 3 : Space Optimized DP

Explanation

Instead of storing:

n × target 

Store only:

One DP array 

This reduces memory usage.

Practice

MemoizationTime Complexity: O(n × requiredSum)
Space Complexity: O(n × requiredSum)

Tabulation
Time Complexity: O(n × requiredSum)
Space Complexity: O(n × requiredSum)

Space Optimized DP
Time Complexity: O(n × requiredSum)
Space Complexity: O(requiredSum)

s1 - s2 = target
s1 + s2 = totalSum
=> s1 = (target + totalSum) / 2 

Count subsets with sum = s1