title: Subset-Sum in Linear Time
body: <p>This was a question on our Algorithms final exam.  It's verbatim because the prof let us take a copy of the exam home.</p>
  
  <blockquote>
    <ol>
    <li>(20 points) Let I = {r1,r2,...,rn} be a set of <em>n</em> arbitrary positive integers and the values in <em>I</em> are <strong>distinct</strong>.  <em>I</em> is not given in any sorted order.  Suppose we want to find a subset <em>I'</em> of <em>I</em> such that the total sum of all elements in <em>I'</em> is exactly 100*ceil(n^.5) (each element of <em>I</em> can appear at most once in <em>I'</em>).  Present an O(<em>n</em>) time algorithm for solving this problem.</li>
    </ol>
  </blockquote>
  
  <p>As far as I can tell, it's basically a special case of the knapsack problem, otherwise known as the subset-sum problem ... both of which are in NP and in theory impossible to solve in linear time?  </p>
  
  <p>So ... was this a trick question?</p>
  
  <hr>
  
  <p><a href="https://stackoverflow.com/questions/9809436/fast-solution-to-subset-sum">This SO post</a> basically explains that a pseudo-polynomial (linear) time approximation can be done if the weights are bounded, but in the exam problem the weights aren't bounded and either way given the overall difficulty of the exam I'd be shocked if the prof expected us to know/come up with an obscure dynamic optimization algorithm. </p>