Advertisement
Utkar5hM

perfect sum count

May 29th, 2022
779
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution{
  2.  
  3.     public:
  4.     int perfectSum(int arr[], int n, int sum)
  5.     {
  6.         // Your code goes here
  7.         sort(arr, arr+n);
  8.         int i=0;
  9.         while(i<n && arr[i]==0) i++;
  10.         int*mew= new int[(sum+1)*(n+1)]();
  11.         fill_n(mew, (sum+1)*(n+1), -1);
  12.         return pow(2,i)*recurse(arr, n, sum, mew, n);
  13.     }
  14.      
  15.     int recurse(int arr[], int n, int sum,int* mew, int N){
  16.     if(mew[sum*N +n]!=-1)return mew[sum*N +n];
  17.     if(sum==0)return 1;
  18.     if(n<=0 || arr[n-1]==0) return 0;
  19.     if(arr[n-1]<=sum) {
  20.             int a = recurse(arr,n-1,sum-arr[n-1], mew, N);
  21.             int b = recurse(arr,n-1,sum, mew, N);
  22.             mew[sum*N +n]= a + b;
  23.             return a+b;
  24.         }
  25.     mew[sum*N +n]= recurse(arr,n-1,sum, mew, N);
  26.     return mew[sum*N +n];
  27.     }
  28. };
Advertisement
RAW Paste Data Copied
Advertisement