int solve_tabu(int N ,int arr[],int t){
vector<vector<int>> dp(t+1,vector<int>(N+1,0));
for(int i=0;i<=N;i++){
dp[0][i]=1;
}
for(int Target=0;Target<=t;Target++){
for(int index=N-1;index>=0;index--){
int choice1=0;
if(Target-arr[index]>=0)
choice1=dp[Target-arr[index]][index+1];
//do not choose
int choice2=dp[Target][index+1];
dp[Target][index]= max(choice1,choice2);
}
}
return dp[t][0];
}
int solve_spo(int N, int arr[], int t) {
vector<int> curr(t + 1, 0);
vector<int> next(t + 1, 0);
next[0] = 1; // Initialize to 1 (one way to achieve target 0)
curr[0] = 1;
for (int Target = 0; Target <= t; Target++) {
for (int index = N - 1; index >= 0; index--) {
int choice1 = 0;
if (Target - arr[index] >= 0)
choice1 = next[Target - arr[index]];
// Do not choose
int choice2 = next[Target];
curr[Target] = choice1 || choice2;
}
next = curr;
}
return next[t];
}
int equalPartition(int N, int arr[])
{
int sum=0;
for(int i=0;i<N;i++){
sum+=arr[i];
}
if(sum&1){
return 0;
}
// vector<vector<int>> dp(sum/2+1,vector<int>(N,-1));
// return solve_memo(N,arr,sum/2,0,dp);
// return solve_tabu(N,arr,sum/2);
return solve_spo(N,arr,sum/2);
}
the test case where the diffrence of output observed is 8 6 2 3 10 2 9 10 2
this is the problem of gfg ,https://www.geeksforgeeks.org/problems/subset-sum-problem2014/1
i tried solve_tabu function. it passes all the testcases . but when i try to convert it to space optimised solution it gave erorr in the above test case . pls refer to the problem on geeksforgeeks subset-sum-problem2014