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.

Difficulty: interview

Starter code:

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        

Solutions:
from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        rods = sorted(rods)[::-1]
        n = len(rods)
        psum = rods.copy()
        for i in range(n-1)[::-1]:
            psum[i] += psum[i+1]

        @lru_cache(None)
        def dfs(idx, diff):
            if idx == n:
                return 0 if diff == 0 else -float('inf')
            if diff > psum[idx]:
                return -float('inf')
            return max(dfs(idx+1,diff),dfs(idx+1,diff+rods[idx]),dfs(idx+1,abs(diff-rods[idx]))+min(diff,rods[idx]))
        return dfs(0,0)

class Solution:
    def tallestBillboard(self, rods):
        dp = {0:0}
        for r in rods:
            for diff, y in list(dp.items()):
                dp[diff + r] = max(dp.get(diff + r, 0), y)
                if diff - r >= 0:
                    dp[diff - r] = max(dp.get(diff - r, 0), y + r)
                if r - diff >= 0:
                    dp[r - diff] = max(dp.get(r - diff, 0), y + diff) 
                # dp[abs(diff - r)] = max(dp.get(abs(diff - r), 0), y + min(diff, r)) 
        return dp[0]

from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods):
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            return max(dp(i + 1, s),
                       dp(i + 1, s - rods[i]),
                       dp(i + 1, s + rods[i]) + rods[i])

        return dp(0, 0)

class Solution:
    def tallestBillboard(self, rods):
        mem = {}
        def dp(i, s):
            if (i, s) in mem: return mem[(i, s)]
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            res = max(dp(i + 1, s),
                      dp(i + 1, s - rods[i]),
                      dp(i + 1, s + rods[i]) + rods[i])
            mem[(i,s)] = res
            return res

        return dp(0, 0)


class Solution:
    def exclu(self,nums):
        # whether we can find two elements x and y in nums so that x & y == 0
        n=len(nums)
        if n<=1: return False
        if n<=4:
            for x in nums:
                for y in nums:
                    if x & y ==0: return True
            return False

        set0,set1=set(),set()
        for x in nums:
            if x & 1 : set1.add(x>>1)
            else: set0.add(x>>1)
        if set0:
            if self.exclu(set0): return True
            if set1:  return self.exclu2(set0,set1)
        return False
        
    def exclu2(self,set0,set1):
        # whether we can find x in set0 and y in set1 so that x & y == 0
        # set0 and set1 are not empty
        if len(set0)==0 or len(set1)==0: return False
        if len(set1)==1:
            x=next(iter(set1))
            for y in set0: 
                if x & y ==0: return True
            return False

        if len(set0)==1:
            x=next(iter(set0))
            for y in set1: 
                if x & y ==0: return True
            return False

        if len(set0)<=8 and len(set1)<=8:
            for x in set0:
                for y in set1:
                    if x & y ==0: return True
            return False

        set00,setx0,set01,set11=set(), set(), set(), set() 
        for x in set0:
            setx0.add(x>>1)
            if x & 1 ==0: set00.add(x>>1)
        for x in set1:
            if x & 1 : set11.add(x>>1)
            else: set01.add(x>>1)
        
        if set00 and set11 and self.exclu2(set00,set11): return True
        if set01 and setx0 and self.exclu2(set01,setx0): return True
        return False

    def tallestBillboard(self, rods: List[int]) -> int:
        n=len(rods)
        if n<=1: return 0
        
        t=sum(rods)
        m=t//2
        infos=[[] for _ in range(m+1)]
        infos[0]=[0]
        
        b=1
        for x in rods:
            # print(f'x={x}')
            for y in range(m-x,-1,-1):
                comb=infos[y]
                if comb:
                    infos[x+y]+=[z+b for z in comb]
            b*=2
            # print(infos)
        
        for y in range(m,0,-1):
            comb,n=infos[y],len(infos[y])
            # print( (y, n, comb)  )
            if n>=2:
                # print( (y, n)  )
                # print(n)
                if self.exclu(comb): return y
        return 0
            


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0:0}
        for x in rods:
            temp = dp.copy()
            for diff, height in list(dp.items()):
                temp[diff+x] = max(temp.get(diff+x, 0), height)
                temp[abs(x - diff)] = max(temp.get(abs(diff-x), 0), height + min(diff, x))
            dp = temp.copy()
        return dp[0]
    
    


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = collections.defaultdict(int)
        dp[0] = 0
        for x in rods:
            nxt = dp.copy()
            for d, y in dp.items():
                nxt[d + x] = max(nxt.get(x + d, 0), y)
                nxt[abs(d - x)] = max(nxt.get(abs(d - x), 0), y + min(d, x))
            dp = nxt
        return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dic=collections.defaultdict(int)
        dic[0]=0
        for x in rods:
            for diff,val in list(dic.items()):
                dic[diff+x]=max(dic[diff+x],val)
                dic[abs(diff-x)]=max(dic[abs(diff-x)],val+min(x,diff))
        return dic[0]


from functools import lru_cache
from collections import defaultdict

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # Dynamic Programming
        # Let dp[i][s] be the largest score we can get using rods[j] (j >= i), 
        # after previously writing a sum of s.
        # Time  complexity: O(N x S), where N is the length of rods and S is the maximum of sum(rods).
        # Space complexity: O(N x S)
        # @lru_cache(None)
        # def dp(i, s):
        #     if i == len(rods):
        #         return 0 if s == 0 else float(\"-inf\")
        #     return max(dp(i + 1, s),
        #                dp(i + 1, s - rods[i]),
        #                dp(i + 1, s + rods[i]) + rods[i])
        # return dp(0, 0)


        # dp[d] mean the maximum pair of sum we can get with pair difference d
        # For example, if have a pair of sum (a, b) with a > b, then dp[a - b] = b
        # If we have dp[diff] = a, it means we have a pair of sum (a, a + diff).
        # And this is the biggest pair with difference = a
        dp = defaultdict(int)
        dp[0] = 0
        for x in rods:
            for d, y in list(dp.copy().items()):
                dp[d + x] = max(dp[d + x], y)
                dp[abs(d - x)] = max(dp[abs(d - x)], y + min(d, x))
        return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}
        for x in rods:
            for d,y in list(dp.items()):
                dp[d + x] = max(dp.get(x + d, 0), y)
                dp[abs(d - x)] = max(dp.get(abs(d - x), 0), y + min(d, x))
        return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp=defaultdict(lambda: -1)
        dp[0]=0
        for x in rods:
            prevdp=dp.copy()
            for d in list(prevdp.keys()):
                dp[x+d]=max(dp[x+d],prevdp[d])
                dp[abs(x-d)]=max(dp[abs(x-d)],prevdp[d]+min(x,d))
        return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}
        for x in rods:
            new_dp = dp.copy()
            for d, y in dp.items():
                new_dp[d + x] = max(new_dp.get(x + d, 0), y)
                new_dp[abs(d - x)] = max(new_dp.get(abs(d - x), 0), y + min(d, x))
            dp = new_dp
        return dp[0]

from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        rods = sorted(rods)
        n = len(rods)
        psum = rods.copy()
        for i in range(n-1)[::-1]:
            psum[i] += psum[i+1]

        @lru_cache(None)
        def dfs(idx, diff):
            if idx == n:
                return 0 if diff == 0 else -float('inf')
            if diff > psum[idx]:
                return -float('inf')
            return max(dfs(idx+1,diff),dfs(idx+1,diff+rods[idx]),dfs(idx+1,abs(diff-rods[idx]))+min(diff,rods[idx]))
        return dfs(0,0)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # dp[diff] = a: have a pair of (a, a + diff)
        
        dp = {0: 0}
        for rod in rods:
            for d, x in list(dp.items()):
                dp[d + rod] = max(dp.get(d + rod, 0), x)
                dp[abs(d - rod)] = max(dp.get(abs(d - rod), 0), x + min(d, rod))
        
        return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        s = sum(rods)
        n = len(rods)
        
        # diff, max_height
        dp = {0:0}
        
        for num in rods:
            new_dp = dp.copy()
            for d,max_h in list(dp.items()):
                new_dp[d+num] = max(new_dp.get(d+num,0),max_h+num)
                new_dp[abs(d-num)] = max(new_dp.get(abs(d-num),0),max(max_h,max_h-d+num))
            dp = new_dp
        return dp[0]
        


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}
        for r in rods:
            for d, t in list(dp.items()):
                dp[r+d] = max(dp.get(r+d, 0), t)
                dp[abs(r-d)] = max(dp.get(abs(r-d), 0), t + min(r, d))
        return dp[0]



class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = collections.defaultdict(int)
        dp[0] = 0
        for x in rods:
            nxt = dp.copy()
            for d, y in dp.items():
                nxt[d + x] = max(nxt.get(x + d, 0), y)
                nxt[abs(d - x)] = max(nxt.get(abs(d - x), 0), y + min(d, x))
            dp = nxt
        return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        dp = {0: 0}
        for r in rods:
            dp2 = dp.copy()
            for d in list(dp.keys()):
                dp2[d + r] = max(dp2.get(d + r, 0), dp[d])
                dp2[abs(d - r)] = max(dp2.get(abs(d - r), 0), dp[d] + min(d, r))
            dp = dp2
        # print(dp)
        return dp[0]
    
    
        # dp = {0: 0}
        # for x in rods:
        #     for d, y in dp.items():
        #         dp[d + x] = max(dp.get(x + d, 0), y)
        #         dp[abs(d - x)] = max(dp.get(abs(d - x), 0), y + min(d, x))
        # return dp[0]
        
        
        
#         @lru_cache(None)
#         def dp(i, s):
#             if i == len(rods):
#                 return 0 if s == 0 else float(\"-inf\")
#             return max(dp(i + 1, s), dp(i + 1, s - rods[i]), dp(i + 1, s + rods[i]) + rods[i])
        
#         return dp(0, 0)
        
        
        
        
#         dp = {}
#         dp[0] = 0
        
#         for i in rods:
#             cur = collections.defaultdict(int)
#             for s in dp:
#                 cur[s+i] = max(dp[s] + i, cur[s+i])
#                 cur[s] = max(dp[s], cur[s])
#                 cur[s-i] = max(dp[s], cur[s-i])
#             dp = cur
#         return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        #diff: lower length
        dp = {0:0}
        for r in rods:
            new_dp = dp.copy()
            for d,l in dp.items():
                h = d+l
                if r+d not in new_dp:
                    new_dp[r+d] = l
                new_dp[r+d] = max(new_dp[r+d],l)
                if abs(d-r) not in new_dp:
                    new_dp[abs(d-r)] = 0
                new_dp[abs(d-r)] = max(new_dp[abs(d-r)],min(l+r,h))
                
            dp = new_dp
        return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        rods.sort()
        prefixsum = [0]
        for i in rods:
            prefixsum.append(prefixsum[-1] + i)
        s = prefixsum[-1]
        dp = [-1] * (s + 1) * 2
        dp[s] = 0
        for i in range(n - 1, -1, -1):
            new_dp = [-1] * (s + 1) * 2
            for d in range(prefixsum[i] + 1):
                if prefixsum[-1] - prefixsum[i] < d:
                    new_dp[d + s] = new_dp[-d + s] = -1
                    break
                for d in [-d, d]:
                    m = -1
                    if dp[rods[i] + d + s] >= 0:
                        m = max(m, dp[rods[i] + d + s] + rods[i])
                    if dp[d - rods[i] + s] >= 0:
                        m = max(m, dp[d - rods[i] + s])
                    if dp[d + s] >= 0:
                        m = max(m, dp[d + s])
                    new_dp[d + s] = m
            dp = new_dp
        return dp[s]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        rods.sort()
        prefixsum = [0]
        for i in rods:
            prefixsum.append(prefixsum[-1] + i)
        dp = {0: 0}
        for i in range(n - 1, -1, -1):
            new_dp = {}
            for d in range(prefixsum[i] + 1):
                if prefixsum[-1] - prefixsum[i] < d:
                    break
                for d in [-d, d]:
                    a = max(dp.get(rods[i] + d, -rods[i] - 1) + rods[i], dp.get(d - rods[i], -1), dp.get(d, -1))
                    if a != -1:
                        new_dp[d] = a
            dp = new_dp
        return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        rods.sort()
        prefixsum = [0]
        for i in rods:
            prefixsum.append(prefixsum[-1] + i)
        s = prefixsum[-1]
        dp = {0: 0}
        for i in range(n - 1, -1, -1):
            new_dp = {}
            for d in range(prefixsum[i] + 1):
                if prefixsum[-1] - prefixsum[i] < d:
                    break
                for d in [-d, d]:
                    m = -1
                    a = dp.get(rods[i] + d, -1)
                    if a >= 0:
                        m = a + rods[i]
                    new_dp[d] = max(m, dp.get(d - rods[i], -1), dp.get(d, -1))
            dp = new_dp
        return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        deltaBase = {0:0}
        deltaList = [0]
        rods.sort()
        for rod in rods:
            # print(deltaList)
            # print(deltaBase)
            deltaBaseTemp = deltaBase.copy()
            iMax = len(deltaList)
            for i in range(iMax):
                delta = deltaList[i]
                deltaPlus = delta+rod   
                # print(rod, delta, deltaPlus)
                if deltaPlus not in deltaBase:
                    deltaList.append(deltaPlus)
                    deltaBase[deltaPlus] = deltaBaseTemp[delta]
                else:
                    deltaBase[deltaPlus] = max(deltaBase[deltaPlus], deltaBaseTemp[delta])

                
                deltaMinus = delta-rod
                if deltaMinus > 0:
                    if deltaMinus not in deltaBase:
                        deltaList.append(deltaMinus)
                        deltaBase[deltaMinus] = deltaBaseTemp[delta]+ rod
                    else:
                        deltaBase[deltaMinus] = max(deltaBase[deltaMinus], deltaBaseTemp[delta]+ rod)
                else:
                    deltaMinus = -deltaMinus
                    if deltaMinus not in deltaBase:
                        deltaList.append(deltaMinus)
                        deltaBase[deltaMinus] = deltaBaseTemp[delta]+ rod - deltaMinus
                    else:
                        deltaBase[deltaMinus] = max(deltaBase[deltaMinus], deltaBaseTemp[delta]+ rod - deltaMinus)
        #         print(rod, delta, deltaMinus, deltaBaseTemp[delta]+ rod - deltaMinus)
        # print(deltaList)
        # print(deltaBase)
        return deltaBase[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        d = defaultdict(lambda: -math.inf)
        d[0] = 0
        for r in rods:
            e = d.copy()
            for h in list(e.keys())[:]:
                d[h+r], d[abs(h-r)] = max(e[h+2*r]+r, e[h+r], e[h] +
                                          r), max(e[abs(h-r)], e[h]+r, e[abs(abs(h-r)-r)]+r)
        return d[0]//2

from collections import defaultdict


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        diff_to_longer_len = defaultdict(int)
        diff_to_longer_len[0] = 0
        
        for new_L in rods:
            tmp = defaultdict(int)
            for delta_L, L in list(diff_to_longer_len.items()):
                tmp[delta_L + new_L] = max(
                    L + new_L,
                    tmp[delta_L + new_L],
                )
                tmp[abs(delta_L - new_L)] = max(
                    L,  # long
                    L - delta_L + new_L,  # new short
                    tmp[abs(delta_L - new_L)],
                )

            for delta_L, L in list(tmp.items()):
                diff_to_longer_len[delta_L] = max(
                    L,
                    diff_to_longer_len[delta_L],
                )

        return diff_to_longer_len[0]


import collections
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # for each number, there are three possible action, join set 1, join set 2, remove
        recorder = {0: 0}
        for rod in rods:
            generateRecorder = collections.defaultdict(int)
            for record in recorder:
                largeNum = recorder[record]
                generateRecorder[record] = max(generateRecorder[record], largeNum)
                generateRecorder[record + rod] = max(generateRecorder[record + rod], largeNum + rod)
                generateRecorder[abs(rod - record)] = max(generateRecorder[abs(rod - record)], max(largeNum, largeNum - record + rod))
            recorder = generateRecorder
        return recorder[0]

class Solution(object):
    def tallestBillboard(self, rods):
        def make(A):
            states = {(0, 0)}
            for x in A:
                states |= ({(a+x, b) for a, b in states} |
                           {(a, b+x) for a, b in states})

            delta = {}
            for a, b in states:
                delta[a-b] = max(delta.get(a-b, 0), a)
            return delta

        N = len(rods)
        Ldelta = make(rods[:N//2])
        Rdelta = make(rods[N//2:])

        ans = 0
        for d in Ldelta:
            if -d in Rdelta:
                ans = max(ans, Ldelta[d] + Rdelta[-d])
        return ans

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        rods.sort()
        prefixsum = [0]
        for i in rods:
            prefixsum.append(prefixsum[-1] + i)
        s = prefixsum[-1]
        dp = [-1] * (s + 1) * 2
        dp[s] = 0
        for i in range(n - 1, -1, -1):
            new_dp = [-1] * (s + 1) * 2
            for d in range(-prefixsum[i], prefixsum[i] + 1):
                m = -1
                if prefixsum[-1] - prefixsum[i] < d:
                    new_dp[d + s] = -1
                    break
                if dp[rods[i] + d + s] >= 0:
                    m = max(m, dp[rods[i] + d + s] + rods[i])
                if dp[d - rods[i] + s] >= 0:
                    m = max(m, dp[d - rods[i] + s])
                if dp[d + s] >= 0:
                    m = max(m, dp[d + s])
                new_dp[d + s] = m
            dp = new_dp
        return dp[s]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        if not rods:
            return 0
        
        rods.sort()
        l = len(rods)
        
        max_rods = sum(rods) / 2
        
        @lru_cache(maxsize=None)
        def search(idx, diff):
            if idx < 0:
                if diff == 0:
                    return True, 0
                else:
                    return False, 0
            
            f1, v1 = search(idx - 1, diff - rods[idx])
            f2, v2 = search(idx - 1, diff + rods[idx])
            
            if f1 and f2:
                return True, max(v1, v2) + rods[idx]
            elif f1:
                return True, v1 + rods[idx]
            elif f2:
                return True, v2 + rods[idx]
            return search(idx - 1, diff)
            
        return search(l - 1, 0)[1] // 2


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        rods.sort(reverse=True)
        n = len(rods)
        dp = [0 for i in range(n)]
        rsum = 0
        self.result = 0
        
        for i in range(n-1, -1, -1):
            rsum += rods[i]
            dp[i] = rsum
        
        
        def dfs(idx, lsum, rsum):
            if idx >= n:
                if lsum == rsum:
                    self.result = max(self.result, lsum)
                return
            
            if abs(lsum-rsum) >  dp[idx]:
                return
            if lsum+rsum+dp[idx] <= 2 * self.result:
                return
            
            dfs(idx+1, lsum+rods[idx], rsum)
            dfs(idx+1, lsum, rsum+rods[idx])
            dfs(idx+1, lsum, rsum)
            
        dfs(0, 0, 0)
        return self.result

from collections import defaultdict
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        d = defaultdict(int)
        d[0] = 0
        for i in rods:
            for sub, b in list(d.items()):
                d[sub + i] = max(d[sub + i], b + i)
                d[sub - i] = max(d[sub - i], b)
        return d[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        if not rods:
            return 0
        
        rods.sort()
        l = len(rods)
        
        max_rods = sum(rods) / 2
        
        @lru_cache(maxsize=None)
        def search(idx, diff):
            if idx < 0:
                if diff == 0:
                    return True, 0
                else:
                    return False, 0
            
            f1, v1 = search(idx - 1, diff - rods[idx])
            f2, v2 = search(idx - 1, diff + rods[idx])
            
            if f1 and f2:
                return True, max(v1, v2) + rods[idx]
            elif f1:
                return True, v1 + rods[idx]
            elif f2:
                return True, v2 + rods[idx]
            return search(idx - 1, diff)
            
        return search(l - 1, 0)[1] // 2

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        if not rods:
            return 0
        
        rods.sort()
        l = len(rods)
        
        max_rods = sum(rods) / 2
        
        @lru_cache(maxsize=None)
        def search(idx, diff):
            if idx < 0:
                if diff == 0:
                    return True, 0
                else:
                    return False, 0
            
            f1, v1 = search(idx - 1, diff - rods[idx])
            f2, v2 = search(idx - 1, diff + rods[idx])
            
            if f1 and f2:
                return True, max(v1, v2) + rods[idx]
            elif f1:
                return True, v1 + rods[idx]
            elif f2:
                return True, v2 + rods[idx]
            return search(idx - 1, diff)
            
        return search(l - 1, 0)[1] // 2

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        if not rods:
            return 0
        
        rods.sort()
        l = len(rods)
        
        # max_rods = sum(rods) / 2
        
        @lru_cache(maxsize=None)
        def search(idx, diff):
            if idx < 0:
                if diff == 0:
                    return True, 0
                else:
                    return False, 0
            
            f1, v1 = search(idx - 1, diff - rods[idx])
            f2, v2 = search(idx - 1, diff + rods[idx])
            
            if f1 and f2:
                return True, max(v1, v2) + rods[idx]
            elif f1:
                return True, v1 + rods[idx]
            elif f2:
                return True, v2 + rods[idx]
            return search(idx - 1, diff)
            
        return search(l - 1, 0)[1] // 2

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def dp(i, d):
            if i == n:
                return 0 if d == 0 else -1
            result = -1
            a = dp(i + 1, rods[i] + d)
            if a >= 0: result = max(result, a + rods[i])
            a = dp(i + 1, d - rods[i])
            if a >= 0: result = max(result, a)
            a = dp(i + 1, d)
            if a >= 0: result = max(result, a)
            return result
        n = len(rods)
        rods.sort()
        return dp(0, 0)


from functools import lru_cache


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        @lru_cache(None)
        def tallest_support_given_diff_of_pair(n, diff):
            # max(L if (L, L - diff) can be built by rods[:n])
            if n == 0:
                return 0 if diff == 0 else float('-inf')

            L = rods[n - 1]
            no_new_rod = tallest_support_given_diff_of_pair(n - 1, diff)
            if diff >= L:
                new_rod_on_taller = tallest_support_given_diff_of_pair(
                    n - 1,
                    diff - L,
                ) + L
            else:  # diff < rods[n - 1]
                new_rod_on_taller = tallest_support_given_diff_of_pair(
                    n - 1,
                    L - diff,
                ) + diff

            new_rod_on_shorter = tallest_support_given_diff_of_pair(n - 1, diff + L)
            return max(no_new_rod, new_rod_on_taller, new_rod_on_shorter)

        return tallest_support_given_diff_of_pair(len(rods), diff=0)


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        sums_lookup = {}
        sums_lookup[0] = 0
        for rod in rods:
            newMembers = {}

            for key in sums_lookup.keys():
                value = sums_lookup[key]

                if rod + key not in newMembers:
                    newMembers[rod + key] = rod + value
                else:
                    if rod + value > newMembers[rod + key]:
                        newMembers[rod + key] = rod + value

                if key - rod not in newMembers:
                    newMembers[key - rod] = value
                else:
                    if value > newMembers[key - rod]:
                        newMembers[key - rod] = value

                if key not in newMembers:
                    newMembers[key] = value
                else:
                    if value > newMembers[key]:
                        newMembers[key] = value

            for key in newMembers.keys():
                sums_lookup[key] = newMembers[key]

        return sums_lookup[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        ## https://www.youtube.com/watch?v=WqLslW2sFxU
        n = len(rods)
        if n==0:
            return 0
        sum_ = sum(rods)
        dp = [[-1 for j in range(sum_+1)] for i in range(n+1)]
        dp[0][0] = 0
        for i in range(n+1):
            h = rods[i-1]
            for j in range(sum_-h+1):
                if dp[i-1][j]<0: continue ## invalid state
                ## case 1: not used rods[i-1]
                dp[i][j] = max(dp[i][j], dp[i-1][j])
                ## case 2: add to the taller one
                dp[i][j+h] = max(dp[i][j+h], dp[i-1][j])
                ## case 3: add to the shorter one
                dp[i][abs(j-h)] = max(dp[i][abs(j-h)], dp[i-1][j] + min(h, j))
                
                
#         for i in range(n+1):
#             print(dp[i])
            
        return dp[n][0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        rods.sort()
        prefixsum = [0]
        for i in rods:
            prefixsum.append(prefixsum[-1] + i)
        s = prefixsum[-1]
        dp = [-1] * (s + 1) * 2
        dp[s] = 0
        for i in range(n - 1, -1, -1):
            new_dp = [-1] * (s + 1) * 2
            for d in range(-prefixsum[i], prefixsum[i] + 1):
                m = -1
                if prefixsum[-1] - prefixsum[i] < abs(d):
                    new_dp[d + s] = -1
                if dp[rods[i] + d + s] >= 0:
                    m = max(m, dp[rods[i] + d + s] + rods[i])
                if dp[d - rods[i] + s] >= 0:
                    m = max(m, dp[d - rods[i] + s])
                if dp[d + s] >= 0:
                    m = max(m, dp[d + s])
                new_dp[d + s] = m
            dp = new_dp
        return dp[s]


from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # rods = sorted(rods)[::-1]
        n = len(rods)
        psum = rods.copy()
        for i in range(n-1)[::-1]:
            psum[i] += psum[i+1]

        @lru_cache(None)
        def dfs(idx, diff):
            if idx == n:
                return 0 if diff == 0 else -float('inf')
            if diff > psum[idx]:
                return -float('inf')
            return max(dfs(idx+1,diff),dfs(idx+1,diff+rods[idx]),dfs(idx+1,abs(diff-rods[idx]))+min(diff,rods[idx]))
        return dfs(0,0)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def dp(i, d):
            if i == n:
                return d == 0, 0
            result = 0
            f, a = dp(i + 1, rods[i] + d)
            if f: result = max(result, a + rods[i])
            f, a = dp(i + 1, d - rods[i])
            if f: result = max(result, a)
            f, a = dp(i + 1, d)
            if f: result = max(result, a)
            return result != 0, result
        
        n = len(rods)
        rods.sort()
        return dp(0, 0)[1]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        m_sum = sum(rods)//2
        m = [[-2 for i in range(m_sum+1)] for j in range(len(rods))]
        def dfs(i,s1,s2):
            if s1 > m_sum or s2 > m_sum:
                return -1
            if i==len(rods):
                return s1 if s1==s2 else -1
            if m[i][abs(s1-s2)]==-2:
                m[i][abs(s1-s2)]=max(dfs(i+1,s1+rods[i],s2),dfs(i+1,s1,s2+rods[i]),dfs(i+1,s1,s2))-max(s1,s2)
            return m[i][abs(s1-s2)]+(max(s1,s2) if m[i][abs(s1-s2)]!=-1 else 0)                
        return max(0,dfs(0,0,0))

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = collections.defaultdict(lambda:0)
        dp[0]=0
        for rod in rods:
            nextlevel = collections.defaultdict(lambda:0)
            for key,val in list(dp.items()):
                nextlevel[key+rod]=max(nextlevel[key+rod],val+rod)
                nextlevel[key]= max(nextlevel[key],val)
                nextlevel[key-rod]=max(nextlevel[key-rod],val+rod)
            dp = nextlevel
        return dp[0]//2
                
                

        
        


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp={0:0}
        for r in rods:
            newdp=collections.defaultdict(int)
            for d in dp:
                newdp[d+r]=max(newdp[d+r],dp[d]+r)
                newdp[d]=max(newdp[d],dp[d])
                newdp[d-r]=max(newdp[d-r],dp[d])
            dp=newdp
        return dp[0]

from functools import lru_cache


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        
        @lru_cache(None)
        def tallest_support_given_diff_of_pair(n, diff):
            # max(L if (L, L - diff) can be built by rods[:n])
            if n == 0:
                return 0 if diff == 0 else float('-inf')

            L = rods[n - 1]
            no_new_rod = tallest_support_given_diff_of_pair(n - 1, diff)
            new_rod_on_taller = tallest_support_given_diff_of_pair(
                n - 1,
                abs(diff - L),
            ) + min(diff, L)
            new_rod_on_shorter = tallest_support_given_diff_of_pair(n - 1, diff + L)
            return max(no_new_rod, new_rod_on_taller, new_rod_on_shorter)

        return tallest_support_given_diff_of_pair(len(rods), diff=0)


# 956. Tallest Billboard
# version 2, inspired by the quote \"only the difference matters\".

def register (diffs, index, a):
    if index not in diffs:
        diffs[index] = a
    else:
        diffs[index] = max (diffs[index], a)

def get_height (rods):
    diffs = {0: 0}
    for rod in rods:
        new_diffs = {}
        for diff, a in diffs.items ():
            register (new_diffs, diff, a)
            register (new_diffs, diff + rod, a)
            register (new_diffs, diff - rod, a + rod)
        diffs = new_diffs

    return diffs[0]
             
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        return get_height(rods)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = dict()
        dp[0] = 0
        for i in rods:
            cur = collections.defaultdict(int)
            for s in dp:
                cur[s + i] = max(dp[s] + i,cur[s + i])
                cur[s] = max(dp[s],cur[s])
                cur[s-i] = max(dp[s],cur[s-i])
            dp = cur
        return dp[0]

INF = 1 << 60
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = defaultdict(lambda:-INF)
        dp[0] = 0
        
        for a in rods:
            ndp = dp.copy()
            for key, val in dp.items():
                if abs(key + a) <= 5000:
                    ndp[key + a] = max(ndp[key + a], dp[key] + a)
                if abs(key - a) <= 5000:
                    ndp[key - a] = max(ndp[key - a], dp[key] + a)
            dp = ndp
            
        return dp[0] >> 1 if dp[0] >= 0 else 0

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        m = len(rods)
        total = sum(rods)
        dp = [[-1] * (5001) for _ in range(m + 1)]
        dp[0][0] = 0
        # dp[n][i]: means max common height we can achieve of using the first n elements that two
        # piles have the hight difference of i
        for i in range(1, m + 1):
            h = rods[i - 1]
            for j in range(5001 - h):
                if dp[i - 1][j] < 0:
                    continue
                dp[i][j] = max(dp[i][j], dp[i - 1][j])
                dp[i][j + h] = max(dp[i - 1][j], dp[i][j + h])
                dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(h, j))
        
        return dp[m][0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        m_sum=sum(rods)//2
        m = [[-2 for i in range(m_sum+1)] for j in range(len(rods))]
        def dfs(i,s1,s2):
            if s1 > m_sum or s2 > m_sum:
                return -1
            if i==len(rods):
                return s1 if s1==s2 else -1
            if m[i][abs(s1-s2)]==-2:
                m[i][abs(s1-s2)]=max(dfs(i+1,s1,s2),dfs(i+1,s1+rods[i],s2),dfs(i+1,s1,s2+rods[i]))-max(s1,s2)
            return m[i][abs(s1-s2)]+(0 if m[i][abs(s1-s2)]==-1 else max(s1,s2))
        return max(0,dfs(0,0,0))

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = dict()
        dp[0] = 0
        
        for i in rods:
            cur = collections.defaultdict(int)
            for s in dp:
                cur[s+i] = max(dp[s] + i, cur[s+i])
                cur[s] = max(dp[s], cur[s])
                cur[s-i] = max(dp[s], cur[s-i])
                
            dp = cur
        return dp[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            return max(dp(i + 1, s),
                       dp(i + 1, s - rods[i]),
                       dp(i + 1, s + rods[i]) + rods[i])

        return dp(0, 0)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        prefix = [0]
        rods.sort(reverse=True)
        for rod in rods:
            prefix.append(prefix[-1]+rod)
        @lru_cache(None)
        def find(i, diff):
            if i < 0:
                return 0 if diff==0 else -float('inf')
            if diff > prefix[-1]-prefix[i]:
                return -float('inf')
            return max(
                find(i-1, diff-rods[i])+rods[i],
                find(i-1, diff+rods[i]),
                find(i-1, diff)
            )
        return find(len(rods)-1, 0)

class Solution:
    def tallestBillboard(self, rods):
            sums_lookup = {0:0} # current sum is zero, length of left rod is 0
            for rod in rods:
                cur = collections.defaultdict(int)
                # consider 3 cases. Rod is aded to the left bucket, rod is added to the right
                # bucket rod is discarded. In all three cases, update length of the left support
                # beam, however, if new sum already exists, make sure we keep the one
                # with longest left support.
                for current_sum, left_support_length in sums_lookup.items():
                    # add rod to the left bucket. Sum will increase since left bucket is 
                    # represented by positive numbers. Left support beam is longer now
                    cur[current_sum+rod] = max(left_support_length + rod, cur[current_sum+rod])
                    # add rod to the right bucket. Sum will decrease since right bucket is
                    # represented by negative numbers. Left support beam is unchanged.
                    cur[current_sum-rod] = max(left_support_length, cur[current_sum-rod])
                    # discard rod. Sum and left support beam is unchanged
                    cur[current_sum] = max(left_support_length, cur[current_sum])
                sums_lookup = cur
            # our goal is to find sum of all elements in the representation array,
            # that adds up to 0, meaning sum of positivel rods (left bucket) is equal to 
            # sum of all negative rods (right bucket)
            return sums_lookup[0]

from collections import defaultdict

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        memo = defaultdict(int)
        memo[0] = 0
        
        for rod in rods:
            temp_memo = defaultdict(int)
            keys = list(memo.keys())
            for k in keys:
                temp_memo[k + rod] = max(memo[k] + rod, temp_memo[k + rod])
                temp_memo[k - rod] = max(memo[k], temp_memo[k - rod])
                temp_memo[k] = max(memo[k], temp_memo[k])
            memo.update(temp_memo)
        return memo[0]
                
        


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # print(rods)
        dp = {0: 0}
        for rod in rods:
            cur = dp.copy()
            for k, v in dp.items():
                cur[k + rod] = max(v + rod, cur.get(k+rod, 0))
                cur[k - rod] = max(v, cur.get(k-rod, 0))
                cur[k] = max(v, cur.get(k, 0))
            dp = cur
        # print(dp)
        return dp[0]

from collections import defaultdict
from copy import copy
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        memo = defaultdict(int)
        memo[0] = 0
        
        for rod in rods:
            temp_memo = defaultdict(int)
            keys = list(memo.keys())
            for k in keys:
                temp_memo[k + rod] = max(memo[k] + rod, temp_memo[k + rod])
                temp_memo[k - rod] = max(memo[k], temp_memo[k - rod])
                temp_memo[k] = max(memo[k], temp_memo[k])
            memo.update(temp_memo)
        return memo[0]
                
        


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(maxsize=None)
        def solve(i: int, s: int) -> int:            
            if i >= len(rods):
                return 0 if s == 0 else -math.inf
            
            return max(solve(i + 1, s), solve(i + 1, s - rods[i]), rods[i] + solve(i + 1, s + rods[i]))
        
        return 0 if math.isinf(res := solve(0, 0)) else res

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = collections.defaultdict(int)
        dp[0]=0
        for rod in rods:
            nextlevel = collections.defaultdict(int)
            for key,val in list(dp.items()):
                nextlevel[key+rod]=max(nextlevel[key+rod],val+rod)
                nextlevel[key]=max(nextlevel[key],val)
                nextlevel[key-rod]=max(nextlevel[key-rod],val+rod)
            dp=nextlevel
        return dp[0]//2


from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            return max(dp(i+1, s),
                       dp(i+1, s - rods[i]),
                       dp(i+1, s+rods[i]) + rods[i])
        return dp(0, 0)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            return max(dp(i + 1, s),
                       dp(i + 1, s - rods[i]),
                       dp(i + 1, s + rods[i]) + rods[i])

        return dp(0, 0)


from functools import lru_cache
class Solution:
    def tallestBillboard(self, rods):
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            return max(dp(i + 1, s),
                       dp(i + 1, s - rods[i]),
                       dp(i + 1, s + rods[i]) + rods[i])

        return dp(0, 0)


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = defaultdict(int)
        dp[0] = 0
        for rod in rods:
            for dif, hi in list(dp.items()):
                lo = hi - dif
                ndif = abs(rod - dif)
                dp[ndif] = max(dp[ndif], hi, lo + rod)
                ndif = rod + dif
                dp[ndif] = max(dp[ndif], rod + hi) 
        return dp[0]

class Solution:
    def tallestBillboard(self, rods):
        dp = dict()
        dp[0] = 0
        
        for i in rods:
            cur = collections.defaultdict(int)
            for s in dp:
                cur[s+i] = max(dp[s] + i, cur[s+i])
                cur[s] = max(dp[s], cur[s])
                cur[s-i] = max(dp[s], cur[s-i])
            dp = cur
        return dp[0]

from functools import lru_cache
import math
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def search(i: int, d: int) -> int:
            if i == 0:
                return 0 if d == 0 else -math.inf
            ans = max(search(i - 1, d), search(i - 1, d + rods[i - 1]) + rods[i - 1])
            if rods[i - 1] <= d:
                ans = max(ans, search(i - 1, d - rods[i - 1]))
            if rods[i - 1] >= d:
                ans = max(ans, search(i - 1, rods[i - 1] - d) + rods[i - 1] - d)
            return ans
        
        return search(len(rods), 0)

class Solution:
    def tallestBillboard(self, rods):
        @lru_cache(None)
        def dp(i, s):
            if i == len(rods):
                return 0 if s == 0 else float('-inf')
            # We can either use the rod, give it to the left, or give it to the right
            return max(dp(i + 1, s),
                       dp(i + 1, s - rods[i]) + rods[i],
                       dp(i + 1, s + rods[i]) + rods[i])

        return int(dp(0, 0)/2)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {}
        dp[0] = 0
        
        for i in rods:
            cur = collections.defaultdict(int)
            for s in dp:
                cur[s+i] = max(dp[s] + i, cur[s+i])
                cur[s] = max(dp[s], cur[s])
                cur[s-i] = max(dp[s], cur[s-i])
            dp = cur
        return dp[0]
        
        
#         total = sum(rods)
#         n = len(rods)
#         m = total // 2
#         dp = [0] * (m + 1)
#         for i in range(n):
#             for j in range(m, rods[i] - 1, -1):
#                 dp[j] = max(dp[j], dp[j - rods[i]] + rods[i])
#         print(dp)


import copy
from collections import defaultdict
from typing import List

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = defaultdict(int)
        dp[0] = 0
        for v in rods:
            dp_ = copy.deepcopy(dp)
            for diff, max_v in list(dp.items()):
                dp_[diff + v] = max(dp_[diff+v], dp[diff])

                dp_[abs(diff - v)] = max(dp_[abs(diff-v)], max_v + min(diff,v))

            dp = dp_
        return dp[0]


from collections import defaultdict 
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
      dp = {0: 0}
      
      for rod in rods:
        currents = collections.defaultdict(int)
        for diff in dp:
          currents[diff + rod] = max(dp[diff] + rod, currents[diff + rod])
          currents[diff] = max(dp[diff], currents[diff])
          currents[diff - rod] = max(dp[diff], currents[diff - rod])
        dp = currents
      
      return dp[0]

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        deltaBase = {0:0}
        deltaList = [0]
        for rod in rods:
            deltaBaseTemp = deltaBase.copy()
            iMax = len(deltaList)
            for i in range(iMax):
                delta = deltaList[i]
                deltaPlus = delta+rod   
                if deltaPlus not in deltaBase:
                    deltaList.append(deltaPlus)
                    deltaBase[deltaPlus] = deltaBaseTemp[delta]
                else:
                    deltaBase[deltaPlus] = max(deltaBase[deltaPlus], deltaBaseTemp[delta])
                
                deltaMinus = delta-rod
                if deltaMinus > 0:
                    if deltaMinus not in deltaBase:
                        deltaList.append(deltaMinus)
                        deltaBase[deltaMinus] = deltaBaseTemp[delta]+ rod
                    else:
                        deltaBase[deltaMinus] = max(deltaBase[deltaMinus], deltaBaseTemp[delta]+ rod)
                else:
                    deltaMinus = -deltaMinus
                    if deltaMinus not in deltaBase:
                        deltaList.append(deltaMinus)
                        deltaBase[deltaMinus] = deltaBaseTemp[delta]+ rod - deltaMinus
                    else:
                        deltaBase[deltaMinus] = max(deltaBase[deltaMinus], deltaBaseTemp[delta]+ rod - deltaMinus)
        return deltaBase[0]

from collections import defaultdict


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        diff_to_longer_len = defaultdict(int)
        diff_to_longer_len[0] = 0
        
        def replace_if_larger(dct, key, val):
            dct[key] = max(val, dct[key])

        for new_L in rods:
            tmp = defaultdict(int)
            for dL, L in list(diff_to_longer_len.items()):
                # there are L and L - dL
                # |(new_L + L) - (L - dL)| = new_L + dL
                replace_if_larger(tmp, new_L + dL, new_L + L)
                # |(new_L + L - dL) - L| = |new_L - dL|
                replace_if_larger(tmp, abs(new_L - dL), max(L, new_L + L - dL))

            for dL, L in list(tmp.items()):
                replace_if_larger(diff_to_longer_len, dL, L)

        return diff_to_longer_len[0]


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @lru_cache(None)
        def find(i, diff):
            if i < 0:
                return 0 if diff==0 else -float('inf')
            return max(
                find(i-1, diff-rods[i])+rods[i],
                find(i-1, diff+rods[i]),
                find(i-1, diff)
            )
        return find(len(rods)-1, 0)

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        prefix = [0]
        rods.sort()
        for rod in rods:
            prefix.append(prefix[-1]+rod)
        @lru_cache(None)
        def find(i, diff):
            if i < 0:
                return 0 if diff==0 else -float('inf')
            if diff > prefix[-1]-prefix[i]:
                return -float('inf')
            return max(
                find(i-1, diff-rods[i])+rods[i],
                find(i-1, diff+rods[i]),
                find(i-1, diff)
            )
        return find(len(rods)-1, 0)