Abstract / Summary

Given rods of lengths 1 or 2, determine the tallest possible even-length billboard using all rods.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 52% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “tallest billboard” problem by searching for the greatest possible height that can be built on two supports using a subset of the given rods. The algorithm first orders the rods in descending length, then uses two mutually recursive depth-first searches-one to pick the first support and two to verify that a second support of identical height can be formed from the remaining rods. A loop iterates over candidate heights from the theoretical maximum down to one, stopping as soon as a feasible height is found.

Key Steps

Sorting and Pre-computation

rods.sort(reverse=True)
size = len(rods)
half = sum(rods) // 2          # maximum height that can be achieved on one side
remaining = [sum(rods[i:]) for i in range(size)]

Sorting in descending order places longer rods first, which helps the recursive search prune impossible branches early. The remaining list stores the total length of all rods from each position to the end; this cumulative sum enables a quick check of whether the remaining material can still satisfy a target height.

Recursive Search for the Second Support (two)

@cache
def two(pos, have, need, used):
    if have == need:
        return True
    if have > need or pos == size:
        return False
    if have + remaining[pos] < need:
        return False
    if used & (1 << pos):
        return two(pos + 1, have, need, used)
    next = pos + 1
    while next < size and rods[next] == rods[pos]:
        next += 1
    if two(next, have, need, used):
        return True
    return two(pos + 1, have + rods[pos], need, used)

two attempts to assemble a set of unused rods whose total length equals need. The function returns True as soon as the exact height is reached. It aborts when the current sum exceeds the target, when all rods have been examined, or when the sum of the current length and the maximum possible contribution from the remaining rods (have + remaining[pos]) is still insufficient. The bitmask used marks rods already allocated to the first support, preventing reuse. Identical-length rods are skipped together to avoid redundant work.

Recursive Search for the First Support (one)

@cache
def one(pos, have, need, used):
    if have == need:
        return two(0, 0, need, used)
    if have > need or pos == size:
        return False
    if have + remaining[pos] < need:
        return False
    next = pos + 1
    while next < size and rods[next] == rods[pos]:
        next += 1
    if one(next, have, need, used):
        return True
    return one(pos + 1, have + rods[pos], need, used | (1 << pos))

one builds the first support incrementally. When its accumulated length matches the target, it delegates to two to verify that a disjoint set of rods can form the second support. The same pruning conditions used in two appear here, ensuring that the search does not explore hopeless branches. The bitmask is updated (used | (1 << pos)) only when a rod is taken for the first support.

Iterating Over Candidate Heights

for length in range(half, 0, -1):
    if one(0, 0, length, 0):
        return length
    one.cache_clear()
    two.cache_clear()
return 0

The outer loop tries each possible height from the highest feasible value (half) down to one. As soon as one confirms a valid configuration, that height is returned. Cache clearing after each iteration guarantees that memoization does not leak results between different target heights.

Edge Cases Handled

When the total sum of all rods is odd, the integer division sum(rods) // 2 correctly caps the search at the largest integer that could possibly be duplicated on both sides, preventing unnecessary attempts at impossible heights.

If the list of rods contains many identical lengths, the inner loops that advance next past equal values collapse those duplicates into a single decision point, thereby handling cases with large groups of equal rods without exponential blow-up.

The bitmask used ensures that a rod selected for the first support is never reconsidered for the second support, even when the same length appears multiple times. This correctly addresses scenarios where the same physical rod could otherwise be double-counted.

When the remaining total length (remaining[pos]) is insufficient to meet the target, the algorithm terminates that branch immediately, covering cases where the remaining rods are too short to reach the needed height.

If the input list is empty, size becomes zero, half is zero, and the final return 0 is executed, correctly indicating that no billboard can be built.

Performance Optimizations

The descending sort places the largest rods first, which maximizes the effectiveness of the early-exit checks (have > need and have + remaining[pos] < need). Larger increments to have are evaluated early, causing many branches to be cut off quickly.

The remaining cumulative sum provides a constant-time upper bound on what can still be achieved from any position, allowing the recursion to prune branches that cannot possibly satisfy the target without exploring deeper levels.

Memoization via @cache on both one and two eliminates repeated work for identical sub-problems defined by the tuple (pos, have, need, used). Because the bitmask encodes the exact set of used rods, the cache distinguishes states that differ only by which rods are already allocated, preventing redundant recomputation.

Skipping over consecutive rods of equal length (while next < size and rods[next] == rods[pos]: next += 1) reduces the branching factor dramatically when many rods share the same size. This optimization prevents the algorithm from exploring permutations that are indistinguishable in terms of total length contribution.

Clearing the caches after each candidate height ensures that memoized results are relevant only to the current target, avoiding cross-contamination that could otherwise lead to incorrect early successes or unnecessary cache growth.

Together, these techniques keep the search space manageable even for inputs with dozens of rods, allowing the solution to find the optimal height without exhaustive enumeration of all subsets.

Imagine having a big pile of sticks that are all different lengths. The goal is to build two towers that are exactly the same height using these sticks. Because we want to make the tallest towers possible, we start by testing the biggest height we could possibly reach by adding up all the sticks and splitting that number in half.

To check if a specific height is possible, the code starts picking sticks one by one to see if they fit into a pile. It keeps track of which sticks have already been used so that no stick is used twice. There are two main parts of this process working together. The first part tries to collect a total length of sticks to reach a target height. Once that first pile is finished, the second part carefully looks at all the leftover sticks to see if they can be arranged to create a second pile that matches the height of the first one exactly.

If the math shows that the remaining pile cannot possibly reach the goal, it skips that path to save time. It also groups sticks together to avoid checking the same combinations over and over again. The code tries to make the tallest possible height first. If it cannot find a way to make two equal towers at that height, it just chooses a slightly smaller number and tries the whole process again. Once the code finds a height that works for both towers, it shares that number as the answer. If it tries every single height and nothing works, it concludes that there is no way to make two equal towers.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python			TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java		Python		Go	TS
	LeetcodeHelp	C++	Java		Python
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fsq	C++
	gouthampradhan		Java
	JoshCrozier			JS
	lkwq007				Python
	suxrobGM					C#
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality