0
 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

0

Browse other questions tagged or ask your own question.