[Python-ideas] Haskell envy (Terry Reedy)

[Terry Reedy]

On 4/24/2012 7:10 PM, Hobson Lane wrote:

> And doesn't ordering matter too (for efficiency). A sorted list of the
> positive integers may solve in much less less time, right?

The OP gave the brute-force solution of testing all subsets as a 
justification for adding a powerset iterator. With negative numbers 
allowed (as in this problem), that may be the best one can do.

But if negatives are excluded, sorting allows a pruning strategy. For 
instance, all subsets can be separated in to those with and without the 
2nd highest. For those with the 2nd highest, one only need consider the 
initial slice of numbers <= hi - 2nd_hi. If two numbers add to more than 
the target, then all larger subsets containing the pair can be excluded 
and not generated and summed. One can apply this idea recursively. But 
there is no guarantee of any saving.

-- 
Terry Jan Reedy