Equal Split Subset Sum

You are given an array of positive integers nums. Your task is to determine whether it is possible to divide the array into exactly two non-empty subsets such that the sum of elements in each subset is identical.

Each element in the original array must belong to exactly one of the two subsets — no element can be left out or used in both subsets. The two subsets do not need to be of equal size, and the elements do not need to be contiguous in the original array.

Return true if such a partition exists, and false otherwise.

---

Understanding the Problem

The core challenge is to determine if we can split the given array into two groups where both groups have the same total sum. This is fundamentally a subset sum problem — specifically, we need to find if any subset of the array sums to exactly half of the total array sum.

Key Insight: If the total sum of all elements is S, then for a valid partition to exist:

1. S must be even (an odd sum cannot be split into two equal integer halves)
2. There must exist a subset of elements that sums to S/2

If we can find such a subset, the remaining elements will automatically sum to S/2 as well, giving us our two equal subsets.

---

Approach

Brute Force (Exponential Time): Generate all possible subsets and check if any subset has a sum equal to half the total. This has O(2^n) time complexity and is impractical for larger inputs.

Dynamic Programming (Optimal): This problem can be efficiently solved using dynamic programming, treating it as a 0/1 knapsack variant:

1. Calculate the total sum S. If S is odd, immediately return false.
2. Set the target as S/2.
3. Use a boolean DP array dp[i] where dp[i] represents whether a sum of i is achievable using some subset of the elements.
4. Initialize dp[0] = true (sum of 0 is always achievable with an empty subset).
5. For each number in the array, update the DP array from right to left to avoid using the same element twice.
6. Return dp[target].

Time Complexity: O(n × target) where target = sum/2 Space Complexity: O(target) using 1D DP optimization