Given n numbers, find minimum number of subsets, which of remaining numbers is equal to 0. For example:
{1,1,3,4,5}
result is equal to 3, because we can delete subsets {1,3} (in two ways) or {3,4,5}.
I'm searching for something faster than O(2^n) brute-force.
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.
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[i]]. This recursive relation can be derived from that fact that new element a[i] will be present in subset or not.
If a[i] is not present => any subset of i-1 elements whose xor is 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)
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.
Time : O(nm)
