Given a non-empty array nums containing only positive integers, determine whether the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

<strong>Input:</strong> nums = [1,5,11,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> The array can be split into [1, 5, 5] and [11].

Example 2:

<strong>Input:</strong> nums = [1,2,3,5]
<strong>Output:</strong> false
<strong>Explanation:</strong> The array cannot be split into two subsets with equal sum.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums\[i\] <= 100

Solution Approach:

1. Sum Calculation and Early Termination:

First, compute the total sum of all elements in the array by iterating through it. If the sum is odd, it's impossible to divide the aray into two subsets with equal sums, so return false immediately.

2. Sorting and Boundary Check:

Sort the array in ascending order. This allows for optimization during the dynamic programming phase. Additionally, check if the largest element exceeds half of the total sum. If it does, return false since it's impossible to achieve equal partition.

3. Dynamic Programming Implementation:

Create a boolean array reachable of size target + 1, where reachable\[sum\] indicates whether it's possible to achieve a subset sum equal to sum using elements from the array. Initialize reachable\[0\] to true since zero sum is always achievable with an empty subset.

Iterate through each eleement in the sorted array. For each element, update the reachable array from right to left (from target down to the current element). This reverse iteration ensures each element is used at most once, preventing duplicate counting.

4. Result Verification:

After processing all elements, check if reachable\[target\] is true. If it is, a subset with sum equal to target exists, meaning the remaining elements also sum to target. Return true; otherwise, return false.

The time complexity of this solution is O(n \* target) and space complexity is O(target), where n is the array length and target is half the total sum.

/**
 * Determines whether the given non-empty positive integer array
 * can be partitioned into two subsets with equal sum.
 *
 * @param arr the input non-empty array of positive integers
 * @return true if partition is possible, false otherwise
 */
public boolean canPartition(int[] arr) {
    // Calculate total sum of all elements
    int total = 0;
    for (int value : arr) {
        total += value;
    }
    
    // Odd sum cannot be divided into two equal subsets
    if (total % 2 != 0) {
        return false;
    }
    
    // Sort array for optimized DP processing
    Arrays.sort(arr);
    
    // Largest element cannot exceed half of total sum
    int half = total / 2;
    if (arr[arr.length - 1] > half) {
        return false;
    }
    
    // DP array: reachable[sum] = true means subset with that sum exists
    boolean[] reachable = new boolean[half + 1];
    reachable[0] = true;
    
    // Process each number
    for (int i = 0; i < arr.length; i++) {
        // Traverse backwards to ensure each element used only once
        for (int j = half; j >= arr[i]; j--) {
            reachable[j] = reachable[j] || reachable[j - arr[i]];
        }
    }
    
    return reachable[half];
}