/prog/ challenge

The challenge is to produce an algorithm to solve the Subset-Sum Problem in your language of choice.  To make it somewhat interesting try to make it as efficient as possible and do not copy an existing algorithm but come up with one yourself.

Bonus Points:  Make the algorithm run in polynomial time.

proc subset-sum(Set input)
  Set subsets := powerset(input)
  foreach (subsets as current_subset)
     if sum(current_subset) = 0
        return true
  return false
end

proc sum(Set input)
   sum := 0
   foreach (input.elements as current_element)
      sum := sum + current_element
   return sum
end

O(n log n)