Subset sum problem

Problem Link-https://www.hackerrank.com/contests/ode-to-code-finals/challenges/rahul-and-another-sum

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?

1 Like

N=40 is enough to be pretty sure that it is about meet in the middle - even without thinking on it :slight_smile:

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).

1 Like

can you ellaborate a bit? i have no idea about meetin the middle algo.

Then it is time to google :slight_smile:

Type “meet in the middle subset sum” in Google, and you’ll find a lot of explanations/tutorials.

Thanks Lebron :slight_smile:

//