956. 最高的广告牌

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。

返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。

示例 1：

输入：[1,2,3,6]
输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。

示例 2：

输入：[1,2,3,4,5,6]
输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。

示例 3：

输入：[1,2]
输出：0
解释：没法安装广告牌，所以返回 0。

提示：

1. 0 <= rods.length <= 20
2. 1 <= rods[i] <= 1000
3. sum(rods[i]) <= 5000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/tallest-billboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，但是效果不好，用了状压 dp, 这题范围上再大一些，状压就无法通过了

方法：状压dp

1. 求出所有子集的和

2. 取一半子集的反集的子集，如果两者和相等就加入答案

class Solution {
    public int tallestBillboard(int[] rods) {
        int ans = 0;
        int n = rods.length;
        int s = 0;
        for (int rod : rods) {
            s += rod;
        }

        int[] sums = new int[1 << n];
        int mask = (1 << n);
        for (int i = 1; i < mask; i++){
            int last =Integer.bitCount( (i&(-i))-1);
            int pre = i &(i-1);
            sums[i]=sums[pre]+rods[last];
        }

        for(int i = 1; i < mask/2; i++){
            int reverse = (i^(mask-1));
            int sum = sums[i];

            if(sum<=ans||sum>s/2||sums[reverse]<=ans)continue;

            for(int j = reverse; j > 0; j = (reverse&(j-1))){
                if(sum==sums[j]) {
                    ans = sum;break;
                }
                
            }

        }

        return ans;
    }
}