Minimum sum partition

//Logic:Time complexity : O(N*W) W=total sum of aray
//break the problem in two part,just find all the subset sum possible.Now we have all subset,so search a
//possible subset closest to sum/2 which will give the lowest difference.
//use a dp array of boolean whose all rows except first row denotes an item where all the columns denotes the
//weight is possible or not using till ith items
//eg dp[i][j]=is it possible to get weight j using items (i-1)th of array.
//then in last row,we have all possible subset sum including all the items,so if first subset weight=i,
//second will sum-i,so find minimum difference.

class Solution{

  public:
    int minDifference(int arr[], int n)  {
        long long int sum=0;
        for(int i=0;i<n;i++) sum+=arr[i];
        vector <vector <bool>> dp(n+1,vector<bool> (sum+1,0));
        for(int i=0;i<=n;i++){
            for(int j=0;j<=sum;j++){
                if(j==0) dp[i][j]=true; //if 0 weight is possible to have without including any item
                else if(i==0) dp[i][j]=false; //all the weight from 1 to sum can not be possible with no items
                                           //starting from 1 to sum because for j=0,first if will only get applied
                else if(j>=arr[i-1]){  //if current array element is smaller than current weight,then either it
                    dp[i][j]=(dp[i-1][j] || dp[i-1][j-arr[i-1]]);//can be included or not included.
                }
                //we have used two times i-1 in above condition here because ith element of array
                //can be accessed by i-1 only,i is for dp array but i-1 required for array.


                else dp[i][j]=dp[i-1][j];  //if current array element is greater than the j weight,
                                           //then it can't be included.
            }
        }
        int dif=INT_MAX;
        for(int i=sum/2;i>=0;i--){
            if(dp[n][i]) return abs(i-(sum-i));
        }


    }
};