A bitmask is an integer that uses each bit as a yes or no flag. In minimum_xor_sum, bit j of mask is 1 when nums2[j] is already paired.

Pairing is done one nums1 number at a time, from nums1[0] to the end. After some pairs are made, the remaining cost depends on one fact only: which nums2 numbers are still free. It does not depend on which of them went to which nums1 number, because those pairs are already paid for in dp[mask].

So all orders that use the same set of nums2 numbers reach the same state. There are n! orders, but only 2^n sets. This is the saving. For n = 20, n! is 2,432,902,008,176,640,000 and 2^n is 1,048,576.

The loop never stores which nums1 numbers are paired. It does not need to, because the numbers are paired in order. If bin(mask).count("1") is i, then nums1[0] to nums1[i - 1] are paired and the next one is nums1[i].

This is why the card's invariant reads: dp[mask] pairs the first bin(mask).count("1") numbers of nums1 with the nums2 numbers whose bits are set in mask. The state has one input only, mask, and the index comes from it.

Example: nums1 = [1, 2] and nums2 = [2, 3]. The costs are 1 ^ 2 = 3, 1 ^ 3 = 2, 2 ^ 2 = 0 and 2 ^ 3 = 1. dp[0b00] = 0. From mask = 0b00, i = 0, so dp[0b01] = 3 and dp[0b10] = 2. From mask = 0b01, i = 1, so pairing nums1[1] with nums2[1] gives dp[0b11] = 3 + 1 = 4. From mask = 0b10, pairing nums1[1] with nums2[0] gives 2 + 0 = 2. The final table is [0, 3, 2, 2], and the answer dp[0b11] is 2.

The transition writes dp[mask | (1 << j)] for a bit j that is not yet set. Setting a bit adds 1 << j to the integer, so the new mask is always larger than mask.

A loop that goes from 0 upward therefore reaches every smaller mask before a larger one. When the loop arrives at a mask, every transition that writes into it has already run, so dp[mask] is final. This is the same fill-order argument as in a table, with the integer value of the mask as the order.

A loop that goes downward reads each larger mask while it still holds infinity, and the answer stays at infinity.

There are 2^n states, one for each subset of nums2. Each state tries every free bit j, which is at most n transitions of constant work. The time is O(N * 2^N). The table dp holds 2^n numbers, so the space is O(2^N).

LeetCode limits n to 14 for Minimum XOR Sum of Two Arrays (LC 1879). That gives 14 * 214 = 229,376 transitions, while the brute force over all pairings needs 14!, which is 87,178,291,200.

This is the reason for the trigger "about 20 items or fewer". At n = 20 the table has 1,048,576 entries and about 20,971,520 transitions. At n = 40 the table would not fit in memory.

Some problems, such as visiting every place once, charge a cost between two consecutive items. Then the set of used items is not enough, because the next cost depends on which item came last. The state becomes dp[mask][last], and the time becomes O(N^2 * 2^N).

In Find the Shortest Superstring (LC 943), the cost of appending a string depends on the string before it, so the state keeps last. In Minimum XOR Sum of Two Arrays (LC 1879), the cost of a pair depends only on the two numbers in the pair, so mask alone is enough.