How is this arrived at.Why does A[0...i1] 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(P) = j ^ a[i], then F(P) ^ a[i] = j ? asked 11 Nov '15, 13:45

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 subproblem reduces to $DP[i1][j]$, else if we consider this element then one of the subsets of $A[i..i1]$ 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[i1][j] \hspace{1 mm} \vert \hspace{1 mm}DP[i1][j \oplus A_i]$ I hope you get the idea :) answered 11 Nov '15, 18:31
