# LeetCode 956: Tallest Billboard

## Problem Restatement

We are given an array `rods`.

Each rod has a positive length. We want to build two steel supports of equal height.

Each rod can be used in one of three ways:

1. Put it on the left support.
2. Put it on the right support.
3. Do not use it.

Return the largest possible equal height of the two supports.

If no positive equal-height supports can be built, return `0`.

The official constraints are:

| Constraint | Value |
|---|---|
| `rods.length` | `1 <= rods.length <= 20` |
| `rods[i]` | `1 <= rods[i] <= 1000` |
| `sum(rods[i])` | `<= 5000` |

Source: LeetCode problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `rods` of positive rod lengths |
| Output | Maximum equal support height |
| Rule | Each rod can be used at most once |
| Choice | A rod can go left, go right, or be skipped |

Example function shape:

```python
def tallestBillboard(rods: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
rods = [1, 2, 3, 6]
```

Output:

```python
6
```

Explanation:

We can build two supports:

```python
left  = 1 + 2 + 3 = 6
right = 6
```

So the answer is `6`.

Example 2:

```python
rods = [1, 2, 3, 4, 5, 6]
```

Output:

```python
10
```

Explanation:

One valid construction is:

```python
left  = 2 + 3 + 5 = 10
right = 4 + 6 = 10
```

Example 3:

```python
rods = [1, 2]
```

Output:

```python
0
```

There is no way to build two equal positive supports.

## First Thought: Try Every Assignment

For each rod, we have three choices:

```python
left support
right support
unused
```

With `n` rods, that creates:

```python
3^n
```

possible assignments.

Since `n` can be `20`, this is too large.

We need to compress the state.

## Key Insight

We do not need to know the exact left and right support heights separately.

We only need to know:

1. The difference between the two support heights.
2. The best shorter support height for that difference.

Define:

```python
dp[diff] = best shorter support height
```

where `diff` is the absolute difference between the two support heights.

Example:

```python
dp[3] = 7
```

means:

```python
shorter support = 7
taller support  = 10
difference      = 3
```

If at the end `diff == 0`, both supports have the same height. The value `dp[0]` is the largest equal support height.

## State Transitions

For each rod `x`, and for each existing state:

```python
diff = taller - shorter
shorter = dp[diff]
```

There are three choices.

### Choice 1: Skip the rod

The state stays the same.

```python
new_diff = diff
new_shorter = shorter
```

### Choice 2: Add rod to the taller side

The taller side becomes even taller.

```python
new_diff = diff + x
new_shorter = shorter
```

### Choice 3: Add rod to the shorter side

This is the important case.

Current state:

```python
taller = shorter + diff
```

After adding `x` to the shorter side:

```python
candidate = shorter + x
```

There are two possibilities.

If `x <= diff`, the shorter side remains shorter:

```python
new_diff = diff - x
new_shorter = shorter + x
```

If `x > diff`, the old shorter side becomes taller:

```python
new_diff = x - diff
new_shorter = taller
```

Both cases can be written as:

```python
new_diff = abs(diff - x)
new_shorter = shorter + min(diff, x)
```

Why?

The shorter support increases by the amount that closes the gap. That amount is `min(diff, x)`.

## Algorithm

Start with:

```python
dp = {0: 0}
```

This means both supports have height `0`.

For each rod `x`:

1. Copy the current `dp` into `next_dp`.
2. For each `(diff, shorter)` in the old `dp`:
   - Add `x` to the taller side.
   - Add `x` to the shorter side.
   - Keep the best shorter height for each resulting difference.
3. Replace `dp` with `next_dp`.

At the end, return:

```python
dp[0]
```

## Correctness

We prove that `dp[diff]` stores the maximum possible shorter support height for each height difference after processing some prefix of rods.

Initially, before using any rods, the only possible state is two supports of height `0`. The difference is `0`, and the shorter height is `0`, so `dp[0] = 0` is correct.

Assume the map is correct before processing a rod `x`.

For every existing state, the rod has exactly three valid choices: skip it, place it on the taller support, or place it on the shorter support.

Skipping preserves the state.

Placing `x` on the taller support increases the difference by `x` and leaves the shorter height unchanged.

Placing `x` on the shorter support reduces the gap by up to `x`. If `x` is larger than the gap, the shorter side becomes the taller side. In both cases, the new difference is `abs(diff - x)`, and the shorter height increases by `min(diff, x)`.

These transitions cover every legal use of rod `x`, and no transition uses `x` more than once.

When multiple assignments produce the same difference, keeping only the largest shorter height is safe. A larger shorter height with the same difference is always at least as good for future rods, because it has the same gap and higher support heights.

By induction, after all rods are processed, `dp[0]` is the maximum shorter height among all assignments with equal supports. Since the difference is `0`, that shorter height is also the common support height. Therefore, the algorithm returns the tallest possible billboard.

## Complexity

Let:

```python
S = sum(rods)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * S)` | There are at most `S + 1` possible differences for each rod |
| Space | `O(S)` | The DP map stores one value per possible difference |

The constraints give `S <= 5000`, so this dynamic programming approach fits easily.

## Implementation

```python
class Solution:
    def tallestBillboard(self, rods: list[int]) -> int:
        dp = {0: 0}

        for x in rods:
            current = dict(dp)

            for diff, shorter in current.items():
                taller_diff = diff + x
                dp[taller_diff] = max(
                    dp.get(taller_diff, 0),
                    shorter,
                )

                shorter_diff = abs(diff - x)
                shorter_height = shorter + min(diff, x)

                dp[shorter_diff] = max(
                    dp.get(shorter_diff, 0),
                    shorter_height,
                )

        return dp[0]
```

## Code Explanation

We start with one state:

```python
dp = {0: 0}
```

Both supports have height `0`.

For each rod:

```python
for x in rods:
```

we copy the current map:

```python
current = dict(dp)
```

This matters because each rod can be used only once. We must not let updates from the current rod create more updates using the same rod again.

For each previous state:

```python
for diff, shorter in current.items():
```

we first try putting the rod on the taller side:

```python
taller_diff = diff + x
dp[taller_diff] = max(dp.get(taller_diff, 0), shorter)
```

The difference grows. The shorter support height stays the same.

Then we try putting the rod on the shorter side:

```python
shorter_diff = abs(diff - x)
shorter_height = shorter + min(diff, x)
```

The new difference is the remaining gap after adding the rod to the shorter side.

The shorter height increases only by the part that helps close the old gap:

```python
min(diff, x)
```

Then we keep the best result for that difference:

```python
dp[shorter_diff] = max(dp.get(shorter_diff, 0), shorter_height)
```

Finally:

```python
return dp[0]
```

returns the largest height where both supports are equal.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.tallestBillboard([1, 2, 3, 6]) == 6
    assert s.tallestBillboard([1, 2, 3, 4, 5, 6]) == 10
    assert s.tallestBillboard([1, 2]) == 0

    assert s.tallestBillboard([1, 2, 3, 4]) == 5
    assert s.tallestBillboard([5, 5]) == 5
    assert s.tallestBillboard([1]) == 0
    assert s.tallestBillboard([2, 2, 2, 2]) == 4
    assert s.tallestBillboard([10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,6]` | Basic equal split |
| `[1,2,3,4,5,6]` | Larger valid construction |
| `[1,2]` | No positive equal supports |
| `[1,2,3,4]` | Requires skipping some arrangement choices |
| `[5,5]` | Direct pair |
| `[1]` | Single rod cannot form two supports |
| `[2,2,2,2]` | Repeated equal rods |
| Large rod plus many small rods | Confirms DP can match different subset sizes |