Minimum sum partition

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.75 KB | None | 0 0

copy raw download clone embed print report

// 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);
}
}

RAW Paste Data Copied

// 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);
    }
}