956. Tallest Billboard

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);
    }
}