class Solution {
int max = 0;
public int tallestBillboard(int[] rods) {
int n = rods.length;
int sum = 0;
for (int rod : rods) {
sum += rod;
}
dfs(rods, 0, 0, sum, rods.length - 1);
return max;
}
private void dfs(int[] rods, int left, int right, int remain, int index) {
if (index < 0) {
if (left == right && left > max) {
max = left;
}
return;
}
if (left + right + remain <= 2 * max || Math.abs(left - right) > remain) return;
dfs(rods, left + rods[index], right, remain - rods[index], index - 1);
dfs(rods, left, right + rods[index], remain - rods[index], index - 1);
dfs(rods, left, right, remain - rods[index], index - 1);
}
}