956. Highest billboard pressure DP

956. The highest billboard

You're installing a billboard , And hope it's the highest . This billboard will have two steel supports , One on each side . The height of each steel support must be equal .

You have a bunch of steel bars that can be welded together  rods. for instance , If the length of the reinforcement is  1、2  and  3, Then they can be welded together to form a length of  6  My bracket .

return   The maximum possible installation height of the billboard  . If you can't install billboards , Please return  0 .

Example 1：

 Input ：[1,2,3,6]
 Output ：6
 explain ： We have two disjoint subsets  {1,2,3}  and  {6}, They have the same and  sum = 6.

Example 2：

 Input ：[1,2,3,4,5,6]
 Output ：10
 explain ： We have two disjoint subsets  {2,3,5}  and  {4,6}, They have the same and  sum = 10.

Example 3：

 Input ：[1,2]
 Output ：0
 explain ： Can't install billboards , So back  0.

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/tallest-billboard
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success , But the effect is not good , Used shape pressure dp, The scope of this question is larger , The pressure cannot pass

Method ： Pressure dp

1. Find the sum of all subsets

2. Take the subset of the inverse set of half subset , If the sum of the two is equal, add the answer

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