DP #8 Minimum sum partition

Minimum Sum Partition

Problem Statement: here

Solution:

We saw in the last question DP #7, how we can create a dp to get equal partition. Here, we gonna use that to answer for the absolute minimum difference. Since we know that after the dp table is computed, if dp[sum] =  true, then we can construct that sum using any of the subset. We also know the total sum, so the difference can be computed easily.

Implementation:

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; int a[n]; int ts = 0; for(int i=0;i<n;i++){ cin >> a[i]; ts += a[i]; } bool dp[ts+1]; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i=1;i<=n;i++){ for(int j=ts;j>=a[i-1];j--){ dp[j] = (dp[j] || dp[j-a[i-1]]); } } int ans = INT_MAX; for(int i=0;i<=ts;i++){ if (dp[i]) ans = min(ans,abs(ts - 2*i)); } cout << ans << endl; } }