# 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. };