1
class Solution {
2
  public int tallestBillboard(int[] rods) {
3
    int[] result = new int[1];
4
    dfs(rods, 0, 0, 0, rods.length, result);
5
    return result[0];
6
  }
7

8
  private void dfs(int[] rods, int left, int right, int level, int n, int[] result) {
9
    if (level == n) {
10
      if (left == right) {
11
        result[0] = Math.max(left, result[0]);
12
      }
13
      return;
14
    }
15

16
    dfs(rods, left, right, level + 1, n, result);
17
    dfs(rods, left + rods[level], right, level + 1, n, result);
18
    dfs(rods, left, right + rods[level], level + 1, n, result);
19
  }
20
}