Stuck midway in Sanskar

general
, , ,
1

I have managed to generate all the possible subsets of the required sum.
Here is an idea of where I am :
https://www.facebook.com/ajax/mercury/attachments/photo.php?fbid=1558562517694731&mode=contain&width=176&height=176
Now,since I can’t chose (1,2,3,5) and (1,2,8) together I need K disjoint subsets which I have been thinking on how to get.I initially thought of storing all the pairs in a double dimensional array and then bruteforcing random K subsets if it works out.But I thought I won’t be able to pass within the given time limit so I didn’t apply this logic. This situation is similar to the problem Exact Cover which is NP Complete I guess.
Also,keep DP as far away as possible from the solution because don’t know it much.
Thanks!

2

have a look at the editorials and also look at the comments there .

sanskar editorials

3

People seem to have attempted the problem in a different manner than I have attempted. I want to know if there is a path which leads to the correct output from where I have left off my solution.

4

The link above is broken. However, I think you are doing something this way.

5

Here is my code so far : http://ideone.com/ML0zeR

6

Here is the code till the point I’ve reached :

7

This gives me all subsets of the required sum but since we can’t take both (1,2,3) and (1,5) I need to code it after this step to take into consideration only disjoint k subsets.