折半搜索板子。

看到 $n\le 20$ 部分分，启发我们搜索。

至于 $n\le 40$，把 $n$ 个物品分成两半，先搜索并存下前半段的物品能凑出的所有方案与重量，然后再搜后半段，后半段搜出质量 $m_1$ 时，前半段的重量 $m_0$ 满足 $m_0\le M-m_1$ 的方案都能计入答案。

前半段搜完排个序，后半段搜索时二分即可。

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
int n,mid,m,w[47],s[(1<<20)+7],cnt,ans;

void DFSL(int step,int sum){
	if(step>mid){
		s[++cnt]=sum;
		return ;
	}
	DFSL(step+1,sum);
	DFSL(step+1,sum+w[step]);
} 
void DFSR(int step,int sum){
	if(step>n){
//		cout<<sum<<' ';
		int x=upper_bound(s+1,s+cnt+1,m-sum)-s-1;
		ans+=x;
		return ;
	}
	DFSR(step+1,sum);
	DFSR(step+1,sum+w[step]);
} 
signed main(){
	cin>>n>>m;
	mid=n/2;
	for(int i=1;i<=n;i++) cin>>w[i];
	DFSL(1,0);
	sort(s+1,s+cnt+1);
//	for(int i=1;i<=cnt;i++) cout<<s[i]<<' ';
//	cout<<'\n';
	DFSR(mid+1,0);
	cout<<ans;
	return 0;
}