Dividing valuable items so that two persons get the most similar value possible
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.