# You are installing a billboard and want it to have the largest height.  The billboard will have two steel supports,
# one on each side.  Each steel support must be an equal height.
#
# You have a collection of rods which can be welded together.  For example, if you have rods of lengths 1, 2, and 3,
# you can weld them together to make a support of length 6.
#
# Return the largest possible height of your billboard installation.  If you cannot support the billboard, return 0.
#
#
#
# Example 1:
#
# Input: [1,2,3,6]
# Output: 6
# Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
# Example 2:
#
# Input: [1,2,3,4,5,6]
# Output: 10
# Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
# Example 3:
#
# Input: [1,2]
# Output: 0
# Explanation: The billboard cannot be supported, so we return 0.
#
#
# Note:
#
# 0 <= rods.length <= 20
# 1 <= rods[i] <= 1000
# The sum of rods is at most 5000.


class Solution(object):
    def tallestBillboard_tle(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """

        def helper(target):
            mask = (1 << len(rods))
            for i in xrange(1, mask):
                curSum = 0
                for j in xrange(0, len(rods)):
                    if i & (1 << j):
                        curSum += rods[j]
                if curSum == 2 * target:
                    # print target, bin(i)
                    for t in xrange(1, i):
                        if not (t & i):
                            continue
                        k, temp, l = t, 0, 0
                        while k:
                            if k & 1:
                                temp += rods[l]
                            l, k = l + 1, k >> 1
                            if temp == target:
                                return True
            return False

        left, right = 0, sum(rods)
        while left < right:
            mid = right - (right - left) / 2
            if helper(mid):
                left = mid
            else:
                right = mid - 1

        return left

    def tallestBillboard(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """
        # dp[i-1][h] : choose first i-1 items, make them into 2 supports with a difference of h, the mininum height of
        # supports
        # we could get a formular like this -
        # 1. assume the ith element is added to the taller support, then the height difference is h + rods[i]
        # the min height won't change, so dp[i][h+rods[i]] = dp[i-1][h]
        # 2. assume the ith elemnt added to the shorter support, there are 2 cases also
        # 2.1, assume after add rods[i] to shorter one, shorter one is longer than previous long one.
        #

        #                rods[i]-h
        #              |
        #       +      |-+ +-+
        #       | h    |     |
        # +-----+      |     |
        # |     |      |     |
        # |     |      |     |
        # |     |      |     |
        # |     |      |     |
        # +     +      +     +
        # difference is rods[i] - h , so dp[i+1][rods[i]-h] = dp[i][h] + h

        # 2. 2 add rods[i] to the shorter one, but still the shorter one is short, then diff = h - rods[i],
        # shorter height is dp[i-1][h] + rods[i], so dp[i+1][h-rods[i]] = dp[i][h] + rods[i]
        #          +                 +
        #          |                 |
        #          |           +-----+
        #          |           |     |  h
        #          | h       rods[i] |
        # + +------+           |-+ +-+
        # |        |           |     |
        # |        |           |     |
        # |        |           |     |
        # |        |           |     |
        # |        |           |     |
        # +        +           +     +
        # we can combine 2.1, 2.1 to dp[i+1][abs(rods[i]-h)] = dp[i][h] + min(h, rods[i]
        s, n = sum(rods), len(rods)
        # at begining, assign dp[0][*] = -1
        dp = [[-1] * (s + 1) for _ in xrange(n + 1)]
        # dp[0][0] means chose nothing, difference is nothing, of course the min of 2 supports is 0
        dp[0][0] = 0
        # dp[0][rods[0]] = 0

        # start from the first item, index based is 1, notice this
        for i in xrange(1, n + 1):
            # record the ith item height
            h = rods[i - 1]
            for j in xrange(0, s - h + 1):
                # if < 0, means i-1 elements is not able to make 2 supports with diff j, then we skip
                if dp[i - 1][j] < 0:
                    continue
                # we could choose not add ith element to left or right supports at all
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
                # we choose to add it to the longer support
                dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j])
                # add to shorter support
                dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(h, j))

        # for d in dp:
        #     print d

        return dp[n][0]

    def tallestBillboard_1d(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """
        # dp[i][h]
        s, n = sum(rods), len(rods)
        dp = [-1] * (s + 1)
        dp[0] = 0

        for i in xrange(1, n + 1):
            h, cur = rods[i - 1], []
            cur.extend(dp)
            for j in xrange(0, s - h + 1):
                if cur[j] < 0:
                    continue
                dp[j] = max(cur[j], dp[j])
                dp[j + h] = max(dp[j + h], cur[j])
                dp[abs(j - h)] = max(dp[abs(j - h)], cur[j] + min(h, j))

        # for d in dp:
        #     print d

        return dp[0]

    def tallestBillboard_dfs_tle(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """

        def dfs(sl, sr, i):
            if i == len(rods):
                if sl == sr:
                    return sl
                return -1
            return max(dfs(sl, sr, i + 1), dfs(sl + rods[i], sr, i + 1), dfs(sl, sr + rods[i], i + 1))

        return dfs(0, 0, 0)

    def tallestBillboard_dfs(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """
        s_max = (sum(rods) >> 1)

        def dfs(sl, sr, i, memo):
            if max(sl, sr) > s_max:
                return -1
            if i == len(rods):
                return sl if sl == sr else -1

            # assume we found a solution : res
            # meme[i][diff] = res - max(sl,sr), for first i elements, when abs(sl-sr) = diff
            # for ex, when i is 4, left = 50, right = 30, and final solution is 200, so we have memo[4][20] = 200-50=150
            # and next time, when i is 4, left = 100, right = 80, then e could have memo[4][20] = 100+150 = 250
            if memo[i][abs(sl - sr)] == -2:
                memo[i][abs(sl - sr)] = max(-1, max(dfs(sl, sr, i + 1, memo), dfs(sl + rods[i], sr, i + 1, memo),
                                                    dfs(sl, sr + rods[i], i + 1, memo)) - max(sl, sr))
            if memo[i][abs(sl - sr)] == -1:
                return -1
            return memo[i][abs(sl - sr)] + max(sl, sr)
            # return memo[i][abs(sl - sr)] + 0 if memo[i][abs(sl - sr)] ==-1 else max(sl,sr)
            # return memo[i][abs(sl - sr)] + max(sl, sr) if memo[i][abs(sl - sr)] != -1 else 0

        memo = [[-2] * (s_max + 1) for _ in xrange(len(rods))]
        return dfs(0, 0, 0, memo)


if __name__ == '__main__':
    print Solution().tallestBillboard([1, 2, 4, 5, 6])
    print Solution().tallestBillboard_dfs([1, 2, 4, 5, 6])
    print Solution().tallestBillboard([1, 2, 3, 4, 5, 6])
    print Solution().tallestBillboard_dfs([1, 2, 3, 4, 5, 6])
    print Solution().tallestBillboard_tle([1, 2, 3, 4, 5, 6])
    # print Solution().tallestBillboard(
    #     [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 50, 50, 50, 150, 150, 150, 100, 100, 100, 123])
    # print Solution().tallestBillboard([1, 2, 4, 8, 16, 32, 64, 128, 256, 512])
    # print Solution().tallestBillboard([1, 2])
    # print Solution().tallestBillboard([1, 2, 4, 5, 6])
    # print Solution().tallestBillboard([2, 4, 8, 16])
    # print Solution().tallestBillboard([1, 2, 3, 6])
