Count Subsets With a Given XOR Value

Given an array of N non-negative integers and a target value K, count how many subsets of the array (including the empty subset, whose XOR is defined to be 0) have XOR of their elements exactly equal to K. The array may contain duplicate values, and different subsets that happen to select the same values at different indices are counted separately.

Input: The first line contains two space-separated integers, N and K. The second line contains N space-separated integers, the array elements. Output: A single integer: the number of subsets whose XOR equals K.

1 <= N <= 20; 0 <= arr[i] <= 1023; 0 <= K <= 1023

This is a great example of DP over a VALUE SPACE (all possible XOR results) rather than over ARRAY INDICES alone - recognizing when a 'count how many ways to achieve each possible outcome' DP applies is a broadly transferable skill (similar in spirit to subset-sum DP).

Count how many subsets of an array have their elements' XOR equal to a specific target value. Brute force: Generate all 2^N subsets directly, compute each one's XOR, and count how many equal the target - this costs O(2^N * N), which is only feasible for the small N <= 20 given here, but the DP approach scales better and is more elegant. Optimised: Tracking a RUNNING COUNT of how many subsets (among those processed so far) achieve EACH possible XOR value lets each new element update all these counts in O(possible XOR values) rather than re-enumerating every subset from scratch - a classic 'counting DP over a bounded value range' technique.

1. Maintain a count array dp[x] = number of subsets formed SO FAR whose XOR equals x, starting with dp[0] = 1 (the empty subset). 2. When processing a new number a, each EXISTING subset either EXCLUDES a (contributing its count to the SAME dp[x]) or INCLUDES it (contributing to dp[x XOR a] instead, since XORing in a new element changes the running XOR). 3. Build a FRESH array for each element processed, so you don't overwrite values you still need to read from the previous step.

Time: O(N * maxXorValue) - for each of the N elements, updating the count array over its full range of possible XOR values (1024 here, since values are bounded by 2^10). Space: O(maxXorValue), for the count array (1024 entries suffice here).

K may be unreachable by any subset, in which case the answer is 0; an array element equal to 0 doubles the count of every currently achievable XOR value, since including or excluding it changes nothing about the XOR.

Be ready to explain why a FRESH array (rather than updating in place) is needed for each element - updating dp[x] and dp[x^a] using values still needed later in the SAME pass would double-count or corrupt intermediate results if done carelessly in place.