1. // User function Template for Java
  2.  
  3. class Solution {
  4.     // idea:
  5.     // 1. Find subset sum
  6.     // 2. Create a array contains the numbers from range which can come in subset
  7.     /**
  8.      * Approach
  9.      * Compute the total sum of all elements in the array.
  10.      * The problem reduces to partitioning the array into two subsets such that the difference of their sums is minimum.
  11.      * Let the sums of the two subsets be S1 and S2. note S2 > S1
  12.      * Since: S1 + S2 = totalSum, diff = S2-S1
  13.      * The difference becomes: |S2 - S1| = |totalSum - 2*S1|
  14.      * To minimize the difference, S1 should be as close as possible to totalSum / 2.
  15.      * Use Dynamic Programming (Subset Sum) to determine all possible subset sums up to totalSum / 2.
  16.      * Create a DP table t[n+1][sum+1] 
  17.      * Fill the DP table using the subset sum recurrence
  18.      * After filling the table, scan the last row from sum down to 0 to find the largest possible subset sum S1.
  19.      * Compute the minimum difference using: minDifference = totalSum - 2*S1
  20.      * Return the computed minimum difference.
  21.      */
  22.     public int minDifference(int arr[]) {
  23.         int n = arr.length;
  24.  
  25.         // 1️⃣ Total Sum
  26.         // find total sum
  27.         long totalSum = 0;
  28.         for(int ele : arr)
  29.             totalSum += ele;
  30.  
  31.         // because sum1 should lie before half of range
  32.         // 2️⃣ Target Half Range
  33.         int sum = (int)(totalSum/2);
  34.  
  35.         boolean[][] t = new boolean[n+1][sum+1];
  36.  
  37.         // when array size increased but sum remains 0
  38.         for(int i=0; i<n+1; i++)
  39.         {
  40.             t[i][0] = true;
  41.         }
  42.  
  43.         // when sum increased but array is empty
  44.         // With 0 elements, we CAN form sum = 0
  45.         for(int j=1; j<sum+1; j++)
  46.         {
  47.             t[0][j] = false;
  48.         }
  49.  
  50.         // actual code of subset sum to fill dp array
  51.         for(int i=1; i<n+1; i++)
  52.         {
  53.             for(int j=1; j<sum+1; j++)
  54.             {
  55.                 if(arr[i-1] <= j)
  56.                 {
  57.                     boolean pick = t[i-1][j - arr[i-1]];
  58.                     boolean notPick = t[i-1][j];
  59.                     t[i][j] = pick || notPick;
  60.                 }
  61.                 else
  62.                     t[i][j] = t[i-1][j];
  63.             }
  64.         }
  65.  
  66.         // Range - 2(Sum1) ~= (S2 + S1) = Range
  67.         int sum1 = 0;
  68.         // finding all those values who can be included in an array
  69.         for(int i=sum; i>=0; i--)
  70.         {
  71.             if(t[n][i] == true)
  72.             {
  73.                 sum1 = i;
  74.                 break;
  75.             }
  76.         }
  77.         return (int) (totalSum - 2*sum1);
  78.     }
  79. }