Count of Subsets Sum with a Given Sum

PHOTO EMBED

Thu Jun 01 2023 12:48:15 GMT+0000 (Coordinated Universal Time)

Saved by @Ranjan_kumar #c++

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

https://youtu.be/F7wqWbqYn9g