Advertisement
imashutosh51

Subset Sum Problem

Jul 25th, 2022
32
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. //User function template for C++
  2. //TC O(N*W) w=sum of whole array.
  3. //created a dp where column contains sum from 0 to total sum of array
  4. //and row contains elements of all the array,oth row means no elements selected
  5. //logic is simple,either include the curretn element or not
  6. class Solution{  
  7. public:
  8.     bool isSubsetSum(vector<int>arr, int s){
  9.         int sum=0,n=arr.size();
  10.         for(int i=0;i<n;i++) sum+=arr[i];    //found sum of all the items ie. j or column of dp aray
  11.         if(s>sum) return 0;
  12.         if(s==sum) return 1;
  13.         bool dp[n+1][sum+1];
  14.         for(int i=0;i<=n;i++){
  15.             for(int j=0;j<=sum;j++){
  16.                 if(j==0){dp[i][j]=true;}    //0 weight is possible to have without including any item
  17.                 else if(i==0){dp[i][j]=false;} //all the weight from 1 to sum can't be possible with no items
  18.                 else if(arr[i-1]>j){     //if current array element is greater than the j weight,
  19.                     dp[i][j]=dp[i-1][j];  //then it can't be included.
  20.                 }
  21.                 else{             //if current array element is smaller than current weight,then either it can be included
  22.                     dp[i][j]=dp[i-1][j] || dp[i-1][j-arr[i-1]];  //or not incuded.
  23.                 }
  24.             }
  25.         }
  26.         return dp[n][s];
  27.     }
  28. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement