Questions Tagged With subsetshttps://discuss.codechef.com/tags/subsets/?type=rss&user=h1ashdr%40gonquestions tagged <span class="tag">subsets</span>enMon, 15 Dec 2014 20:03:59 +0530Stuck midway in Sanskarhttps://discuss.codechef.com/questions/58434/stuck-midway-in-sanskar<p>I have managed to generate all the possible subsets of the required sum.
Here is an idea of where I am :
<a href="https://www.facebook.com/ajax/mercury/attachments/photo.php?fbid=1558562517694731&mode=contain&width=176&height=176">https://www.facebook.com/ajax/mercury/attachments/photo.php?fbid=1558562517694731&mode=contain&width=176&height=176</a>
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!</p>h1ashdr@gonMon, 15 Dec 2014 20:03:59 +0530https://discuss.codechef.com/questions/58434/stuck-midway-in-sanskarstuckdijointsanskarsubsets