title: Sum-subset with a fixed subset size
body: <p>The <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="noreferrer">sum-subset problem</a> states:</p>
  
  <blockquote>
    <p>Given a set of integers, is there a non-empty subset whose sum is zero? </p>
  </blockquote>
  
  <p>This problem is NP-complete in general. I'm curious if the complexity of this slight variant is known:</p>
  
  <blockquote>
    <p>Given a set of integers, is there a subset of size <code>k</code> whose sum is zero? </p>
  </blockquote>
  
  <p>For example, if <code>k = 1</code>, you can do a binary search to find the answer in <code>O(log n)</code>. If <code>k = 2</code>, then you can get it down to <code>O(n log n)</code> (e.g. see <a href="https://stackoverflow.com/questions/4720271/an-interview-question-of-microsoft-about-finding-pair-of-elements-from-array-who">Find a pair of elements from an array whose sum equals a given number</a>). If <code>k = 3</code>, then you can do <code>O(n^2)</code> (e.g. see <a href="https://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number">Finding three elements in an array whose sum is closest to a given number</a>).</p>
  
  <blockquote>
    <p><strong>Is there a known bound that can be placed on this problem as a function of <code>k</code>?</strong></p>
  </blockquote>
  
  <p>As motivation, I was thinking about this question <a href="https://stackoverflow.com/questions/8914961/how-do-you-partition-an-array-into-2-parts-such-that-the-two-parts-have-equal-av">How do you partition an array into 2 parts such that the two parts have equal average?</a> and trying to determine if it is actually NP-complete. The answer lies in whether or not there is a formula as described above.</p>
  
  <p>Barring a general solution, I'd be very interested in knowing an optimal bound for <code>k=4</code>.</p>