Dividing valuable items so that two persons get the most similar value possible You have n items, each one of those has a certain value, represented here as an integer.
  How do you give to two persons the most similar value?


No comment from me here as my code already contains much documentation.

from itertools import combinations, chain
import doctest

def all_subsets(lst):
    """
    Returns all the possibilities of taking n elements of the
    lst, where n goes from 0 to len(lst) - 1

    &gt;&gt;&gt; list(all_subsets([1,2,3]))
    [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]
    """
    return chain.from_iterable(combinations(lst, i) for i in range(len(lst)))

def partitions(items):
    """
    All the possible ways to divide the items in two.

    &gt;&gt;&gt; list(partitions([1,2,3]))
    [((1,), (2, 3)), ((2,), (1, 3)), ((3,), (1, 2)), ((1, 2), (3,)), ((1, 3), (2,)), ((2, 3), (1,))]
    """
    return ((a,b)
             for a in all_subsets(items)
               for b in all_subsets(items)
                 if set(a).union(set(b)) == set(items) and\
                    not set(a).intersection(set(b)))

def evenly_divide(items):
    """
    You have n items, each one of those has a certain value,
    represented here as an integer.

    How do you give to two persons the most similar value?

    This problem is NP-complete.
    This function finds the optimal solution by bruteforce.

    &gt;&gt;&gt; evenly_divide( [1,2,3] )
    ((3,), (1, 2))
    &gt;&gt;&gt; evenly_divide( [9, 12, 14, 17, 23, 32, 34, 40, 42, 49] )
    ((9, 12, 32, 34, 49), (14, 17, 23, 40, 42))
    """
    def difference(parts):
        first_part, second_part = parts
        return abs(sum(first_part) - sum(second_part))

    return min(partitions(items), key=difference)

def fevenly_divide(items):
    """
    You have n items, each one of those has a certain value,
    represented here as an integer.

    How do you give to two persons the most similar value?

    This problem is NP-complete.

    This function finds an approximate solution by sorting the items, and
    then giving the next item to the most poor guy.

    &gt;&gt;&gt; fevenly_divide( [1,2,3] )
    ([2, 1], [3])
    &gt;&gt;&gt; fevenly_divide( [9, 12, 14, 17, 23, 32, 34, 40, 42, 49] )
    ([42, 40, 32, 14, 9], [49, 34, 23, 17, 12])
    """
    first_guy = []
    second_guy = []
    for item in reversed(sorted(items)):
        if sum(first_guy) &lt; sum(second_guy):
            first_guy.append(item)
        else:
            second_guy.append(item)
    return first_guy, second_guy

if __name__ == "__main__":
    doctest.testmod()
partitions

This is inefficient since 
once you have one person's items you know what the other person's items are - just take the complement.

Also - does this condition really work if two items have the same value?

   if set(a).union(set(b)) == set(items) and\
        not set(a).intersection(set(b)))


For instance, what if the values of the items are [3,3,3,3]?

This suggests that you should partition the item ids - not the item values.

Here is an example of what I'm getting at:

def evenly_divide(vals):
  ids = range(len(vals))
  total = sum(vals)
  half = total / 2

  bestSum = 0
  bestIds = []
  for a in all_subsets(ids):
    s = sum( vals[i] for i in a )
    if 2*s &lt;= total and s &gt; bestSum:
        bestSum = s
        bestIds = a
        if 2*s == total: break -- no need to continue
  return (bestSum, bestIds) # returns items for one person


This is still very inefficient, but it's more direct and concise.