<p>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.</p>

<p>You are given a collection of <code>rods</code> that can be welded together. For example, if you have rods of lengths <code>1</code>, <code>2</code>, and <code>3</code>, you can weld them together to make a support of length <code>6</code>.</p>

<p>Return <em>the largest possible height of your billboard installation</em>. If you cannot support the billboard, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> rods = [1,2,3,6]
<strong>Output:</strong> 6
<strong>Explanation:</strong> We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> rods = [1,2,3,4,5,6]
<strong>Output:</strong> 10
<strong>Explanation:</strong> We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> rods = [1,2]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The billboard cannot be supported, so we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rods.length &lt;= 20</code></li>
	<li><code>1 &lt;= rods[i] &lt;= 1000</code></li>
	<li><code>sum(rods[i]) &lt;= 5000</code></li>
</ul>

/**

rods.length = 20
2**20 = 1M
if you split into pairs, 2**19 = 512K

odd numbers are special:
| A | B |
---------
| 0 | 0 | A and B are even    
| 0 | 1 | A is even, B is odd 
| 1 | 0 | A is odd, B is even 
| 1 | 1 | A and B are odd     
- when A and B are different, there must be at least one odd number remaining
- in any case, the smaller sum must be able to catch up to the larger sum

alternative:
use masks and iterate all possible bits starting from 0x1 to the end
consider the hsb as the most recent bit added, then figure out which of the previous results match the current sum
 */
class Solution {

    static constexpr int MAX_ANS = 2500;

    int doit(const vector<int> & rods, const int sum, const int odd, int i, int A, int B) {
        if (A < B) {
            swap(A, B);
        }

        int diff = A - B;

        if (diff > sum) {
            return 0;
        }

        if (diff == sum) {
            return A;
        }

        int result = diff == 0 ? A : 0;

        if (i == rods.size()) {
            return result;
        }
        
        int odd_count = __builtin_popcount(odd & ~((1 << i) - 1));

        if (diff % 2) {
            if (odd_count == 0) {
                return 0;
            }
        } else if (odd_count == 1 && rods[i] % 2) {
            // skip the odd number
            // because adding it will lead to an invalid result
            return max(result, doit(rods, sum - rods[i], odd, i + 1, A, B));
        }

        int curr = rods[i];

        result = max({
            result,
            doit(rods, sum - curr, odd, i + 1, A, B),
            doit(rods, sum - curr, odd, i + 1, A + curr, B),
            doit(rods, sum - curr, odd, i + 1, A, B + curr)
        });

        return result;
    }

    bool match(const vector<short> &dp, const int criteria, const int target) {
        if (criteria == 0 || target == 0) {
            return false;
        }

        int bits = criteria;

        do {
            if (dp[bits] == target) {
                return true;
            }

            bits = (bits - 1) & criteria;
        } while (bits > 0);

        return false;
    }

public:
    int tallestBillboard(vector<int>& rods) {

        int max_result = 0;
        int odd_bits = 0;

        for (int i = 0; i < rods.size(); i++) {
            max_result += rods[i];

            if (rods[i] % 2) {
                odd_bits |= 1 << i;
            }
        }

        max_result /= 2;

        int num_subsets = 1 << rods.size(); 
        vector<short> dp(num_subsets);
        int result = 0;

        for (int i = 1; i < num_subsets; i++) {
            int hsb_idx = 31 - __builtin_clz(i);
            int sum = dp[i] = dp[i ^ (1 << hsb_idx)] + rods[hsb_idx];

            if (sum <= max_result && sum > result) {
                // find a match
                int criteria = ~i & ((1 << hsb_idx) - 1);

// todo: if criteria sum < sum then we do not have to match
                if (dp[criteria] < sum) {
                    continue;
                }

                if (match(dp, criteria, sum)) {                
                    result = sum;

                    if (result == max_result) {
                        return result;
                    }
                }
            }
        }

        return result;

        // int sum = 0;
        // int odd = 0;
        // for (int i = 0; i < rods.size(); i++) {
        //     sum += rods[i];
        //     odd |= (rods[i] & 1) << i;
        // }

        // return doit(rods, sum, odd, 0, 0, 0);
    }
};
70471