Minimum Sum Partition Geeks For Geeks

 class Solution

{

public int minDifference(int arr[], int n) 

{   int sum=0;

    ArrayList<Integer>aa=new ArrayList<Integer>();

    for(int i=0;i<n;i++){

        sum=sum+arr[i];

    }

   

    boolean t[][]=new boolean[n+1][sum+1];

    for(int i=0;i<n+1;i++){

        for(int j=0;j<sum+1;j++){

            if(i==0){

                t[i][j]=false;

            }

            if(j==0){

                t[i][j]=true;

            }

        }

    }

    

    for(int i=1;i<n+1;i++){

        for(int j=1;j<sum+1;j++){

            if(arr[i-1]>j){

                t[i][j]=t[i-1][j];

            }

            else{

                t[i][j]=(t[i-1][j] || t[i-1][j-arr[i-1]]);

            }

        }

    }

   

    for(int j=0;j<(sum)/2 + 1 ;j++){

         if(t[n][j]==true){

              aa.add(j);

         }

    }

   

    int min=Math.abs(sum-2*aa.get(0));

    for(int i=1;i<aa.size();i++){

        if(min>Math.abs(sum-2*aa.get(i))){

            min=Math.abs(sum-2*aa.get(i));

        }

    }

    return min;

} 

}

TIME: O(N*SUM)[GFG Time: 0.6/9.2]

SPACE:O(N*SUM) 

Thanks for Reading.😇