Dynamic programming (DP)

/////////////Top-down approach ( recursion+memoization )/////////////
class Solution {
public:
    
    int solve(int n, vector<int> &dp)
    {
       if(n<=1) return n;
       if(dp[n]!=-1) return dp[n];
       dp[n]=solve(n-1, dp)+solve(n-2,dp);
       return dp[n];
    } 
    
    int fib(int n) {
        vector<int> dp(n+1, -1);
        return solve(n, dp);
    }
};

/////////////////Bottom-Top approach//////////////////////
class Solution {
public:
    int fib(int n) {
        if(n<=1) return n;
        int dp[n+1];
        for(int i=0;i<=n;i++)
        {
            dp[i]=-1;
        }
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};


///////////////////////Space optimization/////////////////
class Solution {
public:
    int fib(int n) {
        if(n<=1) return n;
        int pr1=0, pr2=1, curr;
        for(int i=2;i<=n;i++)
        {
            curr=pr1+pr2;
            pr1=pr2;
            pr2=curr;
        }
        return curr;
    }
};

//////Top-Down approach / recursion-memoization////
class Solution {
public:
    
    int solve(vector<int>& cost, int n, vector<int> &dp)
    {
        if(n==0) return cost[0];
        if(n==1) return cost[1];
        if(dp[n]!=-1) return dp[n];
        dp[n]=min(solve(cost, n-1,dp),solve(cost, n-2, dp))+cost[n];
        return dp[n];
    }
    
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1, -1);
        int ans=min(solve(cost, n-1, dp),solve(cost, n-2, dp));
        return ans;
    }
};

/////Tabulation / bottom-up approach/////
class Solution {
public:
    
    int solve(vector<int>& cost, int n)
    {
        vector<int> dp(n+1, -1);
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<n;i++)
        {
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[n-1], dp[n-2]);
    }
    
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        
        
        return solve(cost, n);
    }
};

////////space optimization///////
class Solution {
public:
    
    int solve(vector<int>& cost, int n)
    {
        int pr1=cost[0], pr2=cost[1], curr;
        for(int i=2;i<n;i++)
        {
            curr=min(pr1,pr2)+cost[i];
            pr1=pr2;
            pr2=curr;
        }
        return min(pr1, pr2);
    }
    
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        
        
        return solve(cost, n);
    }
};

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(), nums.end());
        return max(nums[0]*nums[1]*nums[n-1], nums[n-1]*nums[n-2]*nums[n-3]);
    }
};

class Solution {
public:
    int tribonacci(int n) {
        int dp[n+4];
        for(int i=0;i<n+1;i++)
        {
            dp[i]=-1;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<n+1;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,-1);
        if(n<1) return 0;
        if(n==1) return nums[0];
        dp[0]=nums[0];
        dp[1]=max(nums[0], nums[1]);
        for(int i=2;i<n;i++)
        {
            dp[i]=max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};

class Solution {
public:
    int mxlcs(string &t1, string &t2, int i, int j,  vector<vector<int>> & dp)
    {
        if(i==t1.size()||j==t2.size()) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        int p=0;
        if(t1[i]==t2[j]) 
        {
            p = 1+mxlcs(t1, t2, i+1, j+1, dp);
        }
        else p = max(mxlcs(t1, t2, i+1, j, dp), mxlcs(t1, t2, i, j+1, dp));
        return dp[i][j]=p;
    }
    
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));
        int ans=mxlcs(text1, text2, 0, 0, dp);
        return ans;
    }
};

class Solution{
public:
      string maxSum(string w,char x[], int b[],int n){
          // code here        
          unordered_map<char,int> mp;
          for(int i=0;i<w.size();i++)
          {
              mp[w[i]]=int(w[i]);
          }
          for(int i=0;i<n;i++)
          {
              mp[x[i]]=b[i];
          }
          vector<int> v(w.size());
          for(int i=0;i<w.size();i++)
          {
              v[i]=mp[w[i]];
          }
          
          int edx=0, mxl=0, mxg=INT_MIN;
          for(int i=0;i<w.size();i++)
          {
              mxl=max(v[i], v[i]+mxl);
              
              if(mxl>mxg)
              {
                  mxg=mxl;
                  edx=i;
              }
          }
          int sdx=edx;
          while(sdx>=0)
          {
              mxg-=v[sdx];
              if(mxg==0) break;
              if(sdx==0) break;
              sdx--;
          }
          
          
          string ans="";
          for(int i=sdx;i<=edx;i++)
          {
              ans+=w[i];
          }
          return ans;
      }
};

class Solution{   
public:

    bool solve(vector<int>&arr, int sum, int curr, int idx, vector<vector<int>>& dp)
    {
        if(curr==sum) return true;
        if(curr>sum||idx==arr.size()) return false;
        if(dp[curr][idx]!=-1) return dp[curr][idx];
        bool ck=false;
        ck=ck|solve(arr, sum, curr+arr[idx], idx+1, dp);
        ck=ck|solve(arr, sum, curr, idx+1, dp);
        return dp[curr][idx]=ck;
        
    }
    
    bool isSubsetSum(vector<int>arr, int sum){
        // code here 
        vector<vector<int>> dp(100000, vector<int> (arr.size(), -1));
       return solve(arr, sum, 0, 0, dp);
    }
};

class Solution {
public:

    bool solve(vector<int>& nums, int sum, int curr, int idx, vector<vector<int>>& dp)
    {
        if(curr==sum) return true;
        if(curr>sum||idx==nums.size()) return false;
        if(dp[curr][idx]!=-1) return dp[curr][idx];
        bool ck=false;

        ck=ck|solve(nums, sum, curr+nums[idx], idx+1, dp);
        ck=ck|solve(nums, sum, curr, idx+1, dp);
        return dp[curr][idx]=ck;
    }

    bool canPartition(vector<int>& nums) {
        int s=0;
        int n=nums.size();
        
        for(int i=0;i<n;i++)
        {
            s+=nums[i];
        }
        vector<vector<int>> dp(s+1, vector<int>(nums.size(), -1));
        if(s%2==1) return false;
        
        else return solve(nums, s/2, 0, 0, dp);

    }
};

#include <bits/stdc++.h>
using namespace std;

int solve(vector<vector<int>>& dp, int idx, int cw, int w, vector<int>& v)
{
   if(cw==w) return ++dp[idx][cw];
   if(cw>w||idx==v.size()) return 0;
   if(dp[idx][cw]!=0) return dp[idx][cw];
   
   return dp[idx][cw]=solve(dp, idx+1, cw+v[idx], w, v)+solve(dp, idx+1, cw, w, v);
}

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	        int n, w;
	        cin>>n>>w;
	        vector<int>a(n);
	        for(int i=0;i<n;i++)
	        {
	           cin>>a[i];
	        }
	        vector<vector<int>> dp(n+1, vector<int>(w+1, 0));
	        int ans = solve(dp, 0, 0, w, a);
	        cout<<ans;
	}
	return 0;
}