956. Tallest Billboard

// Solution (1) dfs: TLE
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);
    }
}

// Solution (2) DP
class Solution {
    public int tallestBillboard(int[] rods) {
        int sum = 0;
        for (int rod : rods) {
            sum += rod;
        }
        
        int[] dp = new int[sum + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        
        for (int rod : rods) {
            int[] current = dp.clone();
            for (int i = 0; i <= sum - rod; i++) {
                if (current[i] < 0) continue;
                
                dp[i + rod] = Math.max(dp[i + rod], current[i]);
                dp[Math.abs(i - rod)] = Math.max(dp[Math.abs(i - rod)], 
                                                current[i] + Math.min(i, rod));
            }
        }
        
        return dp[0];
    }
}