title: Subset Sum algorithm
body: <p>I am working on this problem:</p>
  
  <blockquote>
    <p>The Subset Sum problem takes as input a set <code>X = {x1, x2 ,…, xn}</code> of <code>n</code> integers and another integer <code>K</code>. The problem is to check if there exists a subset <code>X'</code> of <code>X</code> whose elements sum to <code>K</code> and finds the subset if there's any. For example, if <code>X = {5, 3, 11, 8, 2}</code> and <code>K = 16</code> then the answer is <code>YES</code> since the subset <code>X' = {5, 11}</code> has a sum of <code>16</code>. Implement an algorithm for Subset Sum whose run time is at least <code>O(nK)</code>.</p>
  </blockquote>
  
  <p>Notice complexity <code>O(nK)</code>. I think dynamic programming may help.</p>
  
  <p>I have found an exponential time algorithm, but it doesn't help.</p>
  
  <p>Can someone help me solve this problem?</p>