Partition Equal Subset Sum is one of the most important Knapsack Pattern interview questions.

You are given:

nums[] 

Goal:

Determine whether the array can be divided into two subsets having equal sum. 

Example

nums = [1,5,11,5] 

Output:

true 

Explanation:

Total Sum = 22
Target Sum = 11
Subset 1 = [11]
Subset 2 = [1,5,5] 

Both subsets have equal sum.

Key Observation

If total sum is odd:

Answer = false 

Because equal partition is impossible.

If total sum is even:

Target = Total Sum / 2 

Now the problem becomes:

Can we find a subset with sum = Target? 

This is a classic Subset Sum problem.

Approach 1 : Memoization

Explanation

For every number:

Pick it or Skip it

Store results and reuse computations.

Approach 2 : Tabulation

Explanation

State:

dp[i][sum] = Can we make sum using first i elements? 

Transition:

 dp[i][sum] = dp[i-1][sum] || dp[i-1][sum-nums[i]]

Meaning:

Not Pick OR Pick 

Dry Run

Input:

nums = [1,5,11,5] 

Total Sum:

22 

Target:

11 

Possible subset:

[11] 

or

[1,5,5] 

Answer:

true 

Approach 3 : Space Optimized DP

Explanation

Instead of storing:

n × target 

Store only:

One DP array 

Traverse target from right to left to avoid reusing elements.

Practice

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

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

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

If total sum is odd, answer is false.
Otherwise,find a subset whose sum equals total/2.