# Tallest Billboard
**Difficulty:** HARD
[External](https://leetcode.com/problems/tallest-billboard)
Canonical: https://scaleengineer.com/dsa/problems/tallest-billboard
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
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 are given a collection of `rods` that 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:** rods = [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:** rods = [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:** rods = [1,2]
**Output:** 0
**Explanation:** The billboard cannot be supported, so we return 0.

**Constraints:**

* `1 <= rods.length <= 20`
* `1 <= rods[i] <= 1000`
* `sum(rods[i]) <= 5000`

# Approaches
## Recursive Approach with Memoization (Top-Down DP)
This approach uses recursion to explore all possibilities of assigning each rod to one of two supports or discarding it. This is a 3-way choice for each rod. A naive recursion would be `O(3^N)`, which is too slow. We can significantly optimize it by using memoization to store and reuse the results of subproblems, identified by the current rod index and the difference in height between the two supports.
**Time:** O(N * S), where N is the number of rods and S is the total sum. Each state `(index, diff)` is computed once. · **Space:** O(N * S), where N is the number of rods and S is the total sum of rod lengths. This is for the memoization table.
**Pros:** Conceptually straightforward, as it directly models the decision process.; Guaranteed to find the optimal solution.
**Cons:** The space complexity of `O(N * S)` can be large if the total sum of rods is high.; For deep recursion stacks (large N), it might lead to a StackOverflowError, although N is small here.
### Explanation
The core idea is to build the two supports recursively. We define a function, say `solve(index, diff)`, which returns the maximum possible height of the first support we can form using rods from `index` to the end, given that the current difference in heights (`support1 - support2`) is `diff`.

The goal is to find the maximum height where the final difference is 0. The value returned by `solve(0, 0)` will be the answer.

To avoid recomputing results for the same state `(index, diff)`, we use a 2D array `memo` for memoization. The difference `diff` can be negative, so we use an offset (equal to the total sum of all rods) to map it to a non-negative array index. The maximum possible sum is 5000, so the difference can range from -5000 to 5000.

The base case for the recursion is when `index` reaches the end of the `rods` array. If `diff` is 0, it means we have successfully formed two supports of equal height, and we return 0. If `diff` is not 0, this path is invalid, so we return a very small number to indicate failure.

In the recursive step, we explore the three choices and take the maximum value returned from the recursive calls.

```java
class Solution {
    Integer[][] memo;
    int n;
    int[] rods;
    int totalSum;

    public int tallestBillboard(int[] rods) {
        this.n = rods.length;
        this.rods = rods;
        this.totalSum = 0;
        for (int rod : rods) {
            totalSum += rod;
        }
        // memo[index][diff + totalSum]
        memo = new Integer[n][2 * totalSum + 1];
        return solve(0, 0);
    }

    private int solve(int index, int diff) {
        if (index == n) {
            return diff == 0 ? 0 : -5001; // A value smaller than any possible valid height
        }
        // Use totalSum as offset for diff
        if (memo[index][diff + totalSum] != null) {
            return memo[index][diff + totalSum];
        }

        // Option 1: Discard rods[index]
        int res = solve(index + 1, diff);

        // Option 2: Add rods[index] to the second support
        res = Math.max(res, solve(index + 1, diff - rods[index]));

        // Option 3: Add rods[index] to the first support
        res = Math.max(res, rods[index] + solve(index + 1, diff + rods[index]));

        return memo[index][diff + totalSum] = res;
    }
}
```
### Algorithm
- Create a memoization table `memo[n][2*totalSum + 1]`, initialized with a sentinel value to store results of subproblems.
- Implement a recursive function `solve(rods, index, diff)`.
- **Base Case**: If `index` reaches the end of the `rods` array (`index == rods.length`), return `0` if `diff == 0` (indicating balanced supports), otherwise return a very large negative number to signify an invalid path.
- **Memoization Check**: Before computing, check if `memo[index][diff + offset]` already has a computed value. If so, return it.
- **Recursive Step**: Explore the three choices for `rods[index]`:
  1. **Discard**: `solve(index + 1, diff)`.
  2. **Add to support 2**: `solve(index + 1, diff - rods[index])`.
  3. **Add to support 1**: `rods[index] + solve(index + 1, diff + rods[index])`.
- Store the maximum of these three results in the memoization table and return it.
- The initial call to start the process is `solve(rods, 0, 0)`.

## Iterative Dynamic Programming
This approach is an iterative, bottom-up version of the dynamic programming solution. It uses a DP table (or a hash map) to keep track of the maximum height achievable for each possible difference between the two supports. We iterate through each rod and update the DP state based on the choices for that rod. This approach optimizes space compared to the recursive memoized version.
**Time:** O(N * S), where N is the number of rods and S is the total sum. For each rod, we iterate through the existing states in the DP map. · **Space:** O(S), where S is the total sum of rod lengths. The number of keys in the map is bounded by S.
**Pros:** More space-efficient than the top-down memoized recursion.; Avoids potential stack overflow issues.; Very efficient for the given constraints.
**Cons:** The logic can be slightly less intuitive than a direct recursive translation of the problem.; Time complexity is dependent on the sum of rod lengths, which could be large in other problem variations.
### Explanation
We can think of this problem as a variation of the knapsack or subset sum problem. Let `dp[diff]` be the maximum height of the first of the two supports, given that the difference between the two supports is `diff`. We can use a hash map to store these `(difference, height)` pairs, as not all differences will be reachable.

We start with `dp = {0: 0}`, representing an initial state with no rods, zero height, and zero difference. Then, for each rod, we iterate through all the states we have computed so far and generate new states by either adding the current rod to the first support or the second support. Discarding the rod is implicitly handled because we build the new DP state from the previous one.

By iterating through all rods, we effectively explore all possibilities in a structured manner. The final answer is the value associated with a difference of 0, i.e., `dp[0]`, which represents the maximum height when both supports are equal.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int tallestBillboard(int[] rods) {
        // dp: key is difference, value is max height of the first support
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);

        for (int rod : rods) {
            Map<Integer, Integer> newDp = new HashMap<>(dp);
            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
                int diff = entry.getKey();
                int height = entry.getValue();

                // Option 1: Add rod to the first support
                int newDiff1 = diff + rod;
                int newHeight1 = height + rod;
                newDp.put(newDiff1, Math.max(newDp.getOrDefault(newDiff1, 0), newHeight1));

                // Option 2: Add rod to the second support
                // height of first support remains the same
                int newDiff2 = diff - rod;
                newDp.put(newDiff2, Math.max(newDp.getOrDefault(newDiff2, 0), height));
            }
            dp = newDp;
        }

        return dp.getOrDefault(0, 0);
    }
}
```
### Algorithm
- We use a map `dp` where `dp[diff]` stores the maximum height of the first support (`sum1`) for a given difference `diff = sum1 - sum2`.
- Initialize `dp` with a single entry: `dp[0] = 0`. This signifies that with no rods, we can have a difference of 0 with supports of height 0.
- Iterate through each `rod` in the `rods` array.
- In each iteration, create a temporary copy of the current `dp` map, say `newDp`.
- For each `(diff, height)` pair in the original `dp` map:
  1. **Add rod to support 1**: The new difference is `diff + rod`, and the new height for support 1 is `height + rod`. Update `newDp[diff + rod]`. 
  2. **Add rod to support 2**: The new difference is `diff - rod`, and the height of support 1 remains `height`. Update `newDp[diff - rod]`.
- After processing all entries for the current rod, replace `dp` with `newDp`.
- After iterating through all rods, the value `dp[0]` will contain the maximum height of a support where the difference is 0, which is our answer.

## Meet-in-the-Middle
Given the small constraint on the number of rods (`N <= 20`), we can use a meet-in-the-middle strategy. This approach splits the problem into two independent subproblems on two halves of the input array. We generate all possible outcomes for the first half and store them. Then, we generate outcomes for the second half and for each one, we look for a complementary outcome from the first half to form a valid solution. This reduces the time complexity from `O(3^N)` to `O(3^(N/2))`, making it the most efficient method for the given constraints.
**Time:** O(3^(N/2)). Generating each map takes `O(3^(N/2))` time. Combining them takes `O(3^(N/2))` as well. · **Space:** O(3^(N/2)), to store the maps of differences and heights for each half. The number of states is at most `3^(N/2)`.
**Pros:** The most time-efficient solution for the given constraints.; Effectively reduces a high exponential complexity to a manageable one.
**Cons:** More complex to conceptualize and implement compared to the straightforward DP approach.; The space complexity is exponential, `O(3^(N/2))`, which can be large, although it's manageable for N=20.
### Explanation
The problem is equivalent to partitioning the `rods` into three sets: `set1`, `set2`, and `discarded`, such that `sum(set1) == sum(set2)` and `sum(set1)` is maximized.

We split the `rods` array into two halves. For each half, we generate all possible ways to distribute its rods into a local `set1` and `set2`. For each such distribution, we compute the difference `diff = sum1 - sum2` and the height `sum1`. We store these in a map: `map[diff] -> max_sum1`.

After generating these maps for both halves (`map1` and `map2`), we combine the results. A full solution is formed by taking one configuration from the first half `(diff1, sum1_1)` and one from the second half `(diff2, sum1_2)`. For the final supports to be equal, the total differences must cancel out: `diff1 + diff2 = 0`, or `diff2 = -diff1`.

So, we iterate through `map1`. For each `diff1`, we look up `-diff1` in `map2`. If it exists, we have found a valid pair of configurations. The total height of the billboard is `sum1_1 + sum1_2`. We maximize this value over all possible pairs.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int tallestBillboard(int[] rods) {
        int n = rods.length;
        Map<Integer, Integer> map1 = getDiffs(rods, 0, n / 2);
        Map<Integer, Integer> map2 = getDiffs(rods, n / 2, n);

        int maxHeight = 0;
        for (int diff : map1.keySet()) {
            if (map2.containsKey(-diff)) {
                maxHeight = Math.max(maxHeight, map1.get(diff) + map2.get(-diff));
            }
        }
        return maxHeight;
    }

    private Map<Integer, Integer> getDiffs(int[] rods, int start, int end) {
        Map<Integer, Integer> map = new HashMap<>();
        // Base case for recursion: empty subset has diff 0 and height 0
        map.put(0, 0);
        for (int i = start; i < end; i++) {
            int rod = rods[i];
            Map<Integer, Integer> newMap = new HashMap<>(map);
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int diff = entry.getKey();
                int height = entry.getValue();
                // Add to support 1
                newMap.put(diff + rod, Math.max(newMap.getOrDefault(diff + rod, 0), height + rod));
                // Add to support 2
                newMap.put(diff - rod, Math.max(newMap.getOrDefault(diff - rod, 0), height));
            }
            map = newMap;
        }
        return map;
    }
}
```
### Algorithm
- Split the `rods` array into two halves, `A` (from index 0 to `N/2 - 1`) and `B` (from `N/2` to `N-1`).
- Write a helper function, `generate(sub_array)`, that produces all possible `(difference, height)` pairs for that subarray.
  - This function can be implemented recursively. For each rod in the subarray, it explores adding it to support 1, support 2, or discarding it.
  - It returns a map where keys are differences and values are the maximum height of support 1 for that difference.
- Call this function for both halves: `map1 = generate(A)` and `map2 = generate(B)`.
- Initialize `maxHeight = 0`.
- Iterate through each `(diff1, height1)` pair in `map1`.
- For each pair, check if `map2` contains the key `-diff1`. This is the matching condition `diff1 + diff2 = 0`.
- If a match is found, let `height2 = map2.get(-diff1)`. The total height for this combination is `height1 + height2`. Update `maxHeight = max(maxHeight, height1 + height2)`.
- Return `maxHeight`.

# Solutions
### Java

```java
class Solution {
public
  int tallestBillboard(int[] rods) {
    int n = rods.length;
    int s = 0;
    for (int x : rods) {
      s += x;
    }
    int[][] f = new int[n + 1][s + 1];
    for (var e : f) {
      Arrays.fill(e, -(1 << 30));
    }
    f[0][0] = 0;
    for (int i = 1, t = 0; i <= n; ++i) {
      int x = rods[i - 1];
      t += x;
      for (int j = 0; j <= t; ++j) {
        f[i][j] = f[i - 1][j];
        if (j >= x) {
          f[i][j] = Math.max(f[i][j], f[i - 1][j - x]);
        }
        if (j + x <= t) {
          f[i][j] = Math.max(f[i][j], f[i - 1][j + x] + x);
        }
        if (j < x) {
          f[i][j] = Math.max(f[i][j], f[i - 1][x - j] + x - j);
        }
      }
    }
    return f[n][0];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int tallestBillboard(vector<int> &rods) {
    int n = rods.size();
    int s = accumulate(rods.begin(), rods.end(), 0);
    int f[n + 1][s + 1];
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1, t = 0; i <= n; ++i) {
      int x = rods[i - 1];
      t += x;
      for (int j = 0; j <= t; ++j) {
        f[i][j] = f[i - 1][j];
        if (j >= x) {
          f[i][j] = max(f[i][j], f[i - 1][j - x]);
        }
        if (j + x <= t) {
          f[i][j] = max(f[i][j], f[i - 1][j + x] + x);
        }
        if (j < x) {
          f[i][j] = max(f[i][j], f[i - 1][x - j] + x - j);
        }
      }
    }
    return f[n][0];
  }
};

```

### Python

```python
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int: n = len(rods) s = sum(rods) f = [[- inf] * (s + 1) for _ in range(n + 1)] f[0][0] = 0 t = 0 for i, x in enumerate(rods, 1): t += x for j in range(t + 1): f[i][j] = f[i - 1][j] if j >= x: f[i][j] = max(f[i][j], f[i - 1][j - x]) if j + x <= t: f[i][j] = max(f[i][j], f[i - 1][j + x] + x) if j < x: f[i][j] = max(f[i][j], f[i - 1][x - j] + x - j) return f[n][0]

```