algorithm - 此代码如何计算总和为偶数的一组正整数的所有子集？

我在一个TopCoder解决方案中遇到了这段代码，这让我很困惑有一个正偶数和奇数整数的数组列表。我认为它返回了其和是偶数模模模的子集的数目。我相信mod的存在只是为了避免列表太大时溢出，所以如果您保持数字小于32，那么我认为您不需要它。

ArrayList l = { ... positive even and odd integers ... };

int dp[] = {1,0};
for (int i = 0; i < l.size(); ++i) {
        int even = dp[0];
        int odd = dp[1];
        if (l.get(i) % 2 == 0) {
                even *= 2;
                odd *= 2;
        } else {
                even += odd;
                odd = even;
        }
        dp[0] = even % MOD;
        dp[1] = odd % MOD;
}
return (dp[0] - 1 + MOD) % MOD;

如果所有整数都是偶数，那么我认为答案是2^N-1。
但如果至少有一个奇数整数，则答案变为2^（n-1）-1。对吗？如果是，为什么要跟踪偶数/奇数？

最佳答案

这根本不需要迭代程序。假设你的集合有N个元素，k偶，N-k奇然后，k偶数实际上并不相关；它们的2^k组合中的任何一个，连同奇数的偶数和的子集，组合成偶数和。
奇数的多少个组合有偶数和？如果N-k>0，则有2^（N-k-1）所以，你是对的。这是一个编码问题，不是数学问题。
但给出的算法如下：
当n=0时，集合只有一个子集：空集合，其总和为0。所以，从even=1和odd=0开始。现在归纳步骤：假设前k个元素的分区数是even和odd。
如果k+1个数是偶数，则其和为偶数的第一k的任何子集都可以附加（或不附加）k+1个元素，使偶数子集的数目加倍。这同样适用于奇数和的子集。
如果第k+1个数是奇数，则其和为偶数的第一k个数的任何子集都不给出具有第k+1个数的任何新的偶数子集，而如果附加了第k+1个数，则其和为奇数的第一k个数的子集给出具有偶数和的子集。所以，新的even是旧的even和odd的总和同样，newodd也是相同的和，因此newodd等于neweven。
请注意，对于所有k，不管是什么。一旦有一个奇数，这个指数就会变高。

关于algorithm - 此代码如何计算总和为偶数的一组正整数的所有子集？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17453773/