Well using bit masking gives correct results for upto n=27-28,and we can’t use dp approach here…So how to solve this problem for 100 marks?
N=40 is enough to be pretty sure that it is about meet in the middle - even without thinking on it
Generate all subsets for first 20 elements and last 20 elements, now it is all about meet in the middle - for every subset from first group you can find number of valid subsets in second group (using two pointers or binary search).
can you ellaborate a bit? i have no idea about meetin the middle algo.
Then it is time to google
Type “meet in the middle subset sum” in Google, and you’ll find a lot of explanations/tutorials.