XOR with subset.Not understanding the logic of dp!

</>dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]</>

How is this arrived at.Why does A[0…i-1] having value j necessarily mean that A[0…i] should also posses the value j?

And why is this :

if there exists a subset P of A[1…i - 1] such that F§ = j ^ a[i], then F§ ^ a[i] = j ?

1 Like

Let us first solve a simple subtask : Given a set A of n integers and you have listed all the subsets of it

Consider A = \{ 1,2 \} Now P(A) = \{ \phi, \{1\},\{2\},\{1,2\}\}

If we add a element 3 to our current set then, A = \{ 1,2,3 \} and P(A) = \{ \phi, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}

While adding the element 3 we have 2 choices, either we add it to the existing subset or we leave the existing subset as it is

For example, \{1\} will results in 2 subsets, \{1\} and \{1,3\} and similarly for the other subsets

Now considering the original problem, main observation is that XOR value of the subset will be always between 0 to 1023

Let the DP state be (i,j), in which we have considered all the subsets of A[1..i] and j is the possible XOR value

if DP[i][j] is true, the one of the subset of A[1..i] will gives the XOR value j, false otherwise

Now consider the DP[i][j], in this we are considering all subsets of A[1..i], so let us consider the i^{th} element i.e. A_i

If we not consider this element then sub-problem reduces to DP[i-1][j], else if we consider this element then one of the subsets of A[i..i-1] must be XORed to j \oplus A_i , because j \oplus A_i \oplus A_i = j

Thus we can say that DP[i][j] = DP[i-1][j] \hspace{1 mm} \vert \hspace{1 mm}DP[i-1][j \oplus A_i]

I hope you get the idea :slight_smile:

1 Like