Skip to content

Instantly share code, notes, and snippets.

Avatar

isaiah isaiah-perumalla

View GitHub Profile
@isaiah-perumalla
isaiah-perumalla / Amazing-test-solution.md
Last active Aug 29, 2015
Solution to Amazing-test problem from hackerearth
View Amazing-test-solution.md

#Problem

The essence of the problem is given a collection of n items of varying size, let Tsum be the sum of all item sizes. we need to able to answer the question, does a subset of items exist such that the sum of the items in the sumset is equal to K. where K is some integer that satisfies the constraints K <= Tmax and (total-K) <= Tmax . Where Tmax is the maximum time allowed.

#Solution

Brute force approach would be iterate through all the subsets of the items.

Let S1, S2 ... S2n all subsets, we iterate through each subset to see if there exist a subset Sk such that the sum of Sk = K. This approach is guarenteed to be correct, however it is impossibly slow because we have to iterate 2n subsets. since the number of items in the collection can reach 100, in the worst case we would have to examine 2100 subsets this is clearly intractable.