Sejal_Rai_Problem_4

#include <bits/stdc++.h> 
using namespace std;

int minSubsetSumDifference(vector<int>& arr, int n)
{
    if(n==1) return arr[0];
    int sum = 0;
    for(int &x:arr) sum += x;
    int knapsackSum = sum/2;
    vector<vector<int>>dp(n+1,vector<int>(knapsackSum+1));
    for(int i=0;i<=knapsackSum;++i) dp[0][i] = 0;
    for(int i=0;i<=n;++i) dp[i][0] = 1;
    int ansSum = 0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=knapsackSum;++j){
            dp[i][j] = j>=arr[i-1] ? dp[i-1][j] | dp[i-1][j-arr[i-1]] : dp[i-1][j];
            if(i==n && dp[i][j]) ansSum = j;
        }
    }
    return abs(ansSum - (sum-ansSum));
}

int main(){
  vector<int> vec={3, 4, 5, 3, 100, 1, 83, 54, 23, 20};
  cout<<minSubsetSumDifference(vec, vec.size())<<endl;
  return 0;
}