piles.py

class Solution1(object):
    def straight(self, rest, pile1, pile2):
        self.call_cnt += 1

        if not rest:
            return ((abs(sum(pile1) - sum(pile2)), pile1, pile2))

        if sum(pile1) > self.upper_bound or sum(pile2) > self.upper_bound:
            return [1E100]

        case1 = self.straight(rest[1:], pile1 + [rest[0]], pile2)
        case2 = self.straight(rest[1:], pile1, pile2 + [rest[0]])

        if case1[0] < case2[0]:
            return case1
        else:
            return case2

    def solve(self, l):
        self.call_cnt = 0
        self.total = sum(l)
        self.min = min(l)
        self.max = max(l)
        self.upper_bound = max(self.total / 2.0 + self.min, self.max)
        res = self.straight(sorted(l, reverse=True), [], [])
        print(self.call_cnt)
        return res

s = Solution1()

assert s.solve([1, 2, 3, 4])[0] == 0
assert s.solve([1000, 1, 1, 1])[0] == 997
assert s.solve(range(1, 11))[0] == 1
assert s.solve(range(28))[0] == 0