java - 如何求子集中元素的和

Question

我想找到元素能被2整除或者元素之和能被2整除的子集的数量

我已经找到了给定数组的所有可能的子集

for(int i=1;i<=(Math.pow(2,n));i++) //Loop for all 2^n combinations
    {
    for(int j=0;j<n;j++)
        {
            if((i&(1<<j))>0) //This gives the subset of the array

输入:1 2 3输出:3 as {2},{1,3=4},{1,2,3=6}是能被2整除的子集或者其元素之和能被2整除的子集。

Answer 1

根据假设:

• 输入为n(自然数)
• 输出是“偶数子集”的计数(在大小为 n 的自然数序列中)

...(确切的)结果是:

分别(=):

分别(=):

<小时/>

O(log(n)) 算法:

public class Test {


    public static long countSuperClever(int n) {
        return pow(2L, (long) n - 1) - 1L;
    }

    // best thx to https://codingforspeed.com/using-faster-integer-power-in-java/
    private static long pow(long a, long b) {
        long re = 1L;
        while (b > 0) {
            if ((b & 1) == 1) {
                re *= a;
            }
            b >>= 1;
            a *= a;
        }
        return re;
    }

    public static void main(String[] args) {
        for (int i = 3; i < 12; i++) {
            System.out.println(countSuperClever(i));
        }
    }

}

<小时/>

另请参阅:https://math.stackexchange.com/a/1338830/20447