int Solution::solve(const vector &A) {
int sum=0;
for(int i=0;i<A.size();i++) sum+=A[i];
sum/=2;
vector<int> dp(sum+1, INT_MAX);
dp[0]=0;
for(int i=0;i<A.size();i++){
for(int j=sum;j>=A[i];j--){
if(dp[j-A[i]]!=INT_MAX) dp[j]=min(dp[j], dp[j-A[i]]+1);
}
}
for(int i=sum;i>=0 ;i--){
if(dp[i]!=INT_MAX) return dp[i];
}
}
Consider this problem a variation of dividing array into two subsets let sum of first subset be s1 and second subset be s2. Our goal is to minimise |s2-s1|. Here subset 2 will contain all numbers before which we are adding + symbol and subset 1 will contain all numbers with - symbol.
let sum be the total sum of original array.
We know at any point s1 + s2 = sum.
therefore, s2 = sum - s1.
assume s2 > s1
therefore we need to minimise s2-s1
=> sum - 2*s1
=> sum/2 - s1
lets consider this number line
1 … … … sum/2… sum
between 1-sum/2 all combinations will not be possible filter out possible combinations, then calculate minimum number of elements required to build that number hence the number closest to sum/2 will give result.
int Solution::solve(const vector &A) {
int n = A.size();
if(n<=0) return 0;
int inf = INT_MAX;
int sum = 0;
for(int i=0;i<n;i++){
sum += A[i];
}
//vector< vector > dp(1e5+100,vector(n+1,inf))
vector dp(sum+1,inf);
dp[0] = 0;
//cout<<sum<<"\n";
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j–){
if(j-2A[i-1]>=0 && dp[j-2A[i-1]]!=inf){
/if(j==sum){
cout<<j-2A[j-1] <<" “<<dp[j]<<”\n";
}/
dp[j] = min(dp[j],dp[j-2A[i-1]]+1);
}
}
}
//cout<<dp[15]<<"\n";
for(int i=sum;i>=0;i–){
if(dp[i]!=inf){
//cout<<i<<"\n";
return dp[i];
}
}
}
if you don’t want to use sum/2
why it gives wrong ans if we change the inner loop to
for(int j=A[i];j<=sum;j++){
if(dp[j-A[i]]!=INT_MAX) dp[j]=min(dp[j], dp[j-A[i]]+1);@kdsumit04
OP has basically converted it to a 0-1 knapsack problem and is solving it with a single dimensional array.
Go through GFGs 0-1 knapsack algo and try modifying it to use a single dimensional array, you’ll get it.
Basically if we start from the beginning as per your snippet, we might be using the same element multiple times which is erroneous behavior. Starting from the end prevents this. It will be clearer if you go through the above recommended exercise.