956. Tallest Billboard

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.

• dp solution with [difference, sum] pair

c++

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp{{0,0}};
        
        for(auto& n : rods) {
            for(auto& [k, v] : unordered_map<int,int>(dp)) {
                dp[k + n] = max(dp[k + n], v);
                dp[abs(k - n)] = max(dp[abs(k - n)], v + min(k, n));
            }
        }
        
        return dp[0];
    }
};

• trie solution with bit masking

c++

struct Trie {
    Trie* next[2];
    bool eof = false;
    Trie() {
        memset(next, 0, sizeof next);
    }
    
    void insert(int mask, int shift) {
        if(shift < 0) eof = true;
        else {
            bool bit = mask & (1<<shift);
            if(!next[bit]) next[bit] = new Trie();
            next[bit]->insert(mask, shift - 1);
        }
    }
    
    bool query(int mask, int shift) {
        if(shift < 0) return eof;
        else {
            bool bit = mask & (1<<shift);
            if(bit) {
                return next[!bit] ? next[!bit]->query(mask, shift - 1) : false;
            }
            if(next[0] and next[0]->query(mask, shift - 1)) return true;
            if(next[1] and next[1]->query(mask, shift - 1)) return true;
            return false;
        }
    }
};
class Solution {
public:
    int tallestBillboard(vector<int>& A) {
        int n = A.size(), ma = accumulate(begin(A), end(A), 0) / 2;
        vector<vector<int>> dp(ma + 1);
        dp[0] = {0};
        for(int i = 0; i < n; i++) {
            for(int j = ma; j >= A[i]; j--) {
                for(auto& mask : dp[j - A[i]])
                    dp[j].push_back(mask | (1<<i));
            }
        }

        for(int i = ma; i >= 1; i--) {
            Trie* t = new Trie();
            for(auto& bit : dp[i]) {
                if(t->query(bit, n)) return i;
                t->insert(bit, n);
            }
        }

        return 0;
    }
};

• 0/1 knapsack solution

c++

class Solution {
    int helper(vector<int>& A, int mask) {
        int sum = 0, n = A.size(), tot = 0;
        for(int i = 0; i < n; i++) {
            if(mask & (1<<i)) sum += A[i];
            tot += A[i];
        }
        if(tot - sum < sum) return 0;
        
        vector<int> dp(sum + 1, 0);
        dp[0] = 1;
        
        for(int i = 0; i < n; i++) {
            if(mask & (1<<i)) continue;
            for(int j = sum; j >= A[i]; j--) {
                if(dp[j - A[i]]) dp[j] = 1;
            }
        }
        
        return dp[sum] != 0 ? sum : 0;
    }
public:
    int tallestBillboard(vector<int>& A) {
        int res = 0, n = A.size();
        
        for(int i = 1; i < (1<<n); i++) {
            res = max(res, helper(A, i));
        }
        
        return res;
    }
};