yes but the query asks for values upto 10^5 only.so, u dont dont have to care for numbers above 10^5.You have to update the bitset for every incoming x by shifting the bitset and doing or with previous bitset so that the bitset at the new possible sums become 1.you can refer to the snippet below.

bitset<100001> bs;
   bs[0]=1;
   for(int i=0;i<n;++i)
   {
   	int x;
   	scanf("%d",&x);
   	bs|=bs<<x;
   }
   int s[100005]={0};
   for(int i=1;i<=100001;++i)
   	s[i]=s[i-1]+bs[i];
   while(q--)
   {
   	int a,b;
   	scanf("%d%d", &a, &b);
   	printf("%d\n", s[b]-s[a-1]);;
   }

how did u come up with the recurrence?can u give a hint at your approach in finding the recurrence?

[deleted]

i am a beginner in graph theory.can u please explain the working of dfs implementation under maximum bipartite matching header written above?