remove numbers from a list without changing total sum

Question

I have a list of numbers (example: [-1, 1, -4, 5]) and I have to remove numbers from the list without changing the total sum of the list. I want to remove the numbers with biggest absolute value possible, without changing the total, in the example removing [-1, -4, 5] will leave [1] so the sum doesn't change.

I wrote the naive approach, which is finding all possible combinations that don't change the total and see which one removes the biggest absolute value. But that is be really slow since the actual list will be a lot bigger than that.

Here's my combinations code:

from itertools import chain, combinations

def remove(items):
    all_comb = chain.from_iterable(combinations(items, n+1) 
                                   for n in xrange(len(items)))
    biggest = None
    biggest_sum = 0
    for comb in all_comb:
        if sum(comb) != 0:
            continue # this comb would change total, skip
        abs_sum = sum(abs(item) for item in comb)
        if abs_sum > biggest_sum:
            biggest = comb
            biggest_sum = abs_sum
    return biggest

print remove([-1, 1, -4, 5])

It corectly prints (-1, -4, 5). However I am looking for some clever, more efficient solution than looping over all possible item combinations.

Any ideas?

Answer 1

if you redefine the problem as finding a subset whose sum equals the value of the complete set, you will realize that this is a NP-Hard problem, (subset sum)

so there is no polynomial complexity solution for this problem .

Answer 2

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Copyright © 2009 Clóvis Fabrício Costa
# Licensed under GPL version 3.0 or higher

def posneg_calcsums(subset):
    sums = {}
    for group in chain.from_iterable(combinations(subset, n+1) 
                                     for n in xrange(len(subset))):
        sums[sum(group)] = group
    return sums

def posneg(items):
    positive = posneg_calcsums([item for item in items if item > 0])
    negative = posneg_calcsums([item for item in items if item < 0])
    for n in sorted(positive, reverse=True):
        if -n in negative:
            return positive[n] + negative[-n]
    else:
        return None

print posneg([-1, 1, -4, 5])
print posneg([6, 44, 1, -7, -6, 19])

It works fine, and is a lot faster than my first approach. Thanks to Alon for the wikipedia link and ivazquez|laptop on #python irc channel for a good hint that led me into the solution.

I think it can be further optimized - I want a way to stop calculating the expensive part once the solution was found. I will keep trying.