10.Min. subset sum difference

GFG problem link --> https://practice.geeksforgeeks.org/problems/minimum-sum-partition3317/1



//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{

  public:
	int minDifference(int arr[], int n)  { 
	    // Your code goes here
	  
// 	  calculating possible ranges of sum from array elements  
	   int sum=0;
	   for(int i=0;i<n;i++){
	       sum+=arr[i];
	   }
	    
	   //formig the top down matrix 
	   
	   bool dp[n+1][sum+1];
	   
	   for(int i=0;i<n+1;i++){
	       for(int j=0;j<sum+1;j++){
	           if(i==0){
	               dp[i][j]=false;
	           }
	           if(j==0){
	               dp[i][j]=true;
	           }
	       }
	   }
	   
	   //i==n;j==sum
	   for(int i=1;i<n+1;i++){
	       for(int j=1;j<sum+1;j++){
	           
	          if(arr[i-1]<=j){
	              dp[i][j]=dp[i-1][j-arr[i-1]] || dp[i-1][j];
	          } 
	          
	          else{
	              dp[i][j]=dp[i-1][j];
	          }
	           
	       }
	   }
	   
	   
	   //accesing only the last row of the matrix 
	   
	   int res=INT_MAX;
	   
	   for(int j=0;j<=sum/2;j++){
	       if(dp[n][j]==1){
	           res=min(res,sum-(2*j));
	       }
	   }
	   
	   return res;
	    
	} 
};


//{ Driver Code Starts.
int main() 
{
   
   
   	int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        int a[n];
        for(int i = 0; i < n; i++)
        	cin >> a[i];

       

	    Solution ob;
	    cout << ob.minDifference(a, n) << "\n";
	     
    }
    return 0;
}
// } Driver Code Ends