#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; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter