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.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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)
		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):
		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):
		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:
			for y in range(m - x, -1, -1):
				comb = infos[y]
				if comb:
					infos[x + y] += [z + b for z in comb]
			b *= 2
		for y in range(m, 0, -1):
			(comb, n) = (infos[y], len(infos[y]))
			if n >= 2:
				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:
		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:
		s = sum(rods)
		n = len(rods)
		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 = {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
		return dp[0]


class Solution:

	def tallestBillboard(self, rods: List[int]) -> int:
		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:
		deltaBase = {0: 0}
		deltaList = [0]
		rods.sort()
		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]


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, L - delta_L + new_L, 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:
		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:
		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:

		@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):
			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:
				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
				elif rod + value > newMembers[rod + key]:
					newMembers[rod + key] = rod + value
				if key - rod not in newMembers:
					newMembers[key - rod] = value
				elif value > newMembers[key - rod]:
					newMembers[key - rod] = value
				if key not in newMembers:
					newMembers[key] = value
				elif 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:
		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
				dp[i][j] = max(dp[i][j], dp[i - 1][j])
				dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j])
				dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(h, j))
		return dp[n][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 + 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]


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
		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:

		@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}
		for rod in rods:
			cur = collections.defaultdict(int)
			for (current_sum, left_support_length) in sums_lookup.items():
				cur[current_sum + rod] = max(left_support_length + rod, cur[current_sum + rod])
				cur[current_sum - rod] = max(left_support_length, cur[current_sum - rod])
				cur[current_sum] = max(left_support_length, cur[current_sum])
			sums_lookup = cur
		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:
		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
		return dp[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 = 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]


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)


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]


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()):
				replace_if_larger(tmp, new_L + dL, new_L + L)
				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)