// User function Template for Java

class Solution {
    // idea:
    // 1. Find subset sum
    // 2. Create a array contains the numbers from range which can come in subset
    /**
     * Approach
     * Compute the total sum of all elements in the array.
     * The problem reduces to partitioning the array into two subsets such that the difference of their sums is minimum.
     * Let the sums of the two subsets be S1 and S2. note S2 > S1
     * Since: S1 + S2 = totalSum, diff = S2-S1
     * The difference becomes: |S2 - S1| = |totalSum - 2*S1|
     * To minimize the difference, S1 should be as close as possible to totalSum / 2.
     * Use Dynamic Programming (Subset Sum) to determine all possible subset sums up to totalSum / 2.
     * Create a DP table t[n+1][sum+1] 
     * Fill the DP table using the subset sum recurrence
     * After filling the table, scan the last row from sum down to 0 to find the largest possible subset sum S1.
     * Compute the minimum difference using: minDifference = totalSum - 2*S1
     * Return the computed minimum difference.
     */
    public int minDifference(int arr[]) {
        int n = arr.length;
        
        // 1️⃣ Total Sum
        // find total sum
        long totalSum = 0;
        for(int ele : arr)
            totalSum += ele;
        
        // because sum1 should lie before half of range
        // 2️⃣ Target Half Range
        int sum = (int)(totalSum/2);
        
        boolean[][] t = new boolean[n+1][sum+1];
        
        // when array size increased but sum remains 0
        for(int i=0; i<n+1; i++)
        {
            t[i][0] = true;
        }
        
        // when sum increased but array is empty
        // With 0 elements, we CAN form sum = 0
        for(int j=1; j<sum+1; j++)
        {
            t[0][j] = false;
        }
        
        // actual code of subset sum to fill dp array
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<sum+1; j++)
            {
                if(arr[i-1] <= j)
                {
                    boolean pick = t[i-1][j - arr[i-1]];
                    boolean notPick = t[i-1][j];
                    t[i][j] = pick || notPick;
                }
                else
                    t[i][j] = t[i-1][j];
            }
        }
        
        // Range - 2(Sum1) ~= (S2 + S1) = Range
        int sum1 = 0;
        // finding all those values who can be included in an array
        for(int i=sum; i>=0; i--)
        {
            if(t[n][i] == true)
            {
                sum1 = i;
                break;
            }
        }
        return (int) (totalSum - 2*sum1);
    }
}