We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I solved in Haskell and this problem was be cool to optimize. But definitely is not easy, worth much more than just 20 points. My first solution was awful, O(2^n), genereting all subsets. Timed out in almost all cases. So I optimize to O(n*log(n)) (descending sort) + O(n) (search). Better, but a lot of test cases timed out yet. In the end, I need to prepare the data to use a binary search tree on queries, so then, I got all the tests passes with O(log(n)) complexity.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Subset Sum
You are viewing a single comment's thread. Return to all comments →
I solved in Haskell and this problem was be cool to optimize. But definitely is not easy, worth much more than just 20 points. My first solution was awful, O(2^n), genereting all subsets. Timed out in almost all cases. So I optimize to O(n*log(n)) (descending sort) + O(n) (search). Better, but a lot of test cases timed out yet. In the end, I need to prepare the data to use a binary search tree on queries, so then, I got all the tests passes with O(log(n)) complexity.