由于n个数，找到最小数量的子集，其剩余数等于0。例如：

Given n numbers, find minimum number of subsets, which of remaining numbers is equal to 0. For example:

{1,1,3,4,5}

结果等于3，因为我们可以删除子集{1,3}（以两种方式）或{3,4,5}

result is equal to 3, because we can delete subsets {1,3} (in two ways) or {3,4,5}.

我在寻找比O（2 ^ n）的蛮力的东西更快。

I'm searching for something faster than O(2^n) brute-force.

推荐答案

让我们考虑的尺寸N * M，其中M = 10 ^ 4动态规划表。我们有大小为n的数组，这样 1＆LT = A [1] - 。= M

Let us consider a Dynamic Programming table of size n*m where m=10^4. We have an array of size n, such that 1 <= a[i] <= m.

现在， D [I] [j]的=子集的数量，使得该组异或为j 这里所述一组异或装置集合中的所有元素的异或。

Now, D[i][j] = number of subsets such that xor of the set is j Here xor of the set means xor of all elements of set.

D [I] [J] = D [I-1] [J] + D [I-1] [J XOR A [1]] 。这种递归关系可以从这个事实可以推导出新的元素[I]将是present的子集或不。

D[i][j] = D[i-1][j] + D[i-1][j xor a[i]]. This recursive relation can be derived from that fact that new element a[i] will be present in subset or not.

如果A [1]是不是present =>Ⅰ-1的元素，其XOR为j任何子集

If a[i] is not present => any subset of i-1 elements whose xor is j

如果一个[i]为present =>Ⅰ-1的元素，其异或任意子集是ĴXOR A [1] 。（因为ĴXOR A [1] XOR A [1] = j的）

If a[i] is present => any subset of i-1 elements whose xor is j xor a[i].( Because j xor a[i] xor a[i] = j)

在这种方式，您能找到的异或为任何给定数量的所有子集。注意，这个给定的数量可以只一样大米。来到你的问题，它只是归结为找出元素的异或为X，X是所有元素的异或的子集。

In this way you are able to find all the subset whose xor is any given number. Note that this given number can be only as large as m. Coming to your question, it just boils down to finding out subset of elements whose xor is X, where X is xor of all elements.

时间：O（NM）