title: Subset sum with special conditions
body: <p>(Before you reply with a link to another SO question or close this as a duplicate please read the question carefully. This is different than the standard variant of this problem and I've searched for a long time so I'm pretty sure there isn't a question like this here)</p>
  
  <p>I need to find if the <strong>smallest possible S</strong> that is the sum of some <strong>subset of X[i]</strong> that is <strong>>= T</strong> (some target value, smaller than the sum of the full set).</p>
  
  <p>The set isn't very large (about 40 elements), but still too big for exponential backtracking solution.</p>
  
  <p>The <strong>numbers and the sum are huge</strong> (about 10^15), so dynamic programming won't work (The number of possible states is large so the memoization table would soon run out of memory).</p>
  
  <p>For the same reason the linear time algorithm by Pisinger won't work (it's O(nr) where r is the upper bound on the sum, which is too big in this case).</p>
  
  <p>Is there some deterministic algorithm that will help me in this case of large sum but few numbers? I don't want to resort to some approximation algorithm.</p>