I recently came across this problem. There is no official editorial (except for a few short comments in this thread), and I have not been able to find an explanation I understand.

Problem Summary: You are given N (1 <= N <= 24) tennis balls, each located at a distinct lattice point, as well as a tennis basket also located at a lattice point distinct from all other lattice points. At one time, you can hold at most 2 tennis balls. Find the minimum total squared distance it'll take to put all tennis balls in the basket, if you start at the basket. Also:

• Every lattice point is from (-100, -100) to (100, 100)

• The time limit is an unusually high 4 seconds

A O(2^N * N^2) solution is obvious: do a subset/bitmask DP over all N tennis balls. To find dp[i], simply test every individual set bit in the number i, as well as every pair of set bits in the number i (representing taking one and two balls in the previous step), and transition from that previous dp-state. There are 2^N states, and there are O(N^2) pairs of tennis balls for each number, so the overall complexity is O(2^N * N^2).

But N = 24, so this times out. In the comments, they mention a O(2^N * N) solution, where for each dp[i] you only need to test N pairs of tennis balls for transitions. Specifically, they say that for dp[i], we only need to test pairs that contain the first set bit in the number i, which reduces the number of pairs, and therefore the number of transitions, to O(N). Apparently, this approach still manages to cover all possibilities for transitions, but I cannot understand why.

Can someone provide some insights/hints to this problem's solution?