We need a one-to-one assignment of bikes to workers that minimizes the total Manhattan distance. Each worker gets exactly one bike, and since m >= n, some bikes may go unassigned.

This is an assignment problem. Brute force tries every way of distributing bikes over workers. A better approach follows from one fact: if we assign workers in a fixed order (worker 0, then worker 1, and so on), future decisions depend only on which bikes are already taken, not on which worker took which bike. That set of taken bikes fits in a bitmask, and with m at most 10 there are at most 2^10 = 1,024 possible masks, so the entire state space is small enough to enumerate. This is the setup for bitmask dynamic programming.

Key Constraints:

Intuition

Try every possible assignment: for worker 0, try each bike; for worker 1, try each remaining bike; continue until every worker has one. Track which bikes are taken in a boolean array and keep a running total of distances. When all workers are assigned, compare the total against the best one found so far.

This is backtracking over a decision tree where each level corresponds to a worker and each branch corresponds to a bike choice. Branches whose running total already matches or exceeds the best answer cannot improve it, so we prune them.

Algorithm

Example Walkthrough

For workers = [[0,0],[2,1]] and bikes = [[1,2],[3,3]], the pairwise distances are: worker 0 to bike 0 = 3, worker 0 to bike 1 = 6, worker 1 to bike 0 = 2, worker 1 to bike 1 = 3. The first branch assigns bike 0 to worker 0 and bike 1 to worker 1 for a total of 3 + 3 = 6, which becomes the best answer. The second branch assigns bike 1 to worker 0 for a running total of 6; the recursive call for worker 1 prunes immediately because 6 already equals the best total, so the full cost of that branch (6 + 2 = 8) is never computed. The function returns 6.

Code

The backtracking approach reaches the same subproblem state through different orderings and re-solves it each time. The next approach caches the result for each state so no state is solved twice.

Intuition

Backtracking repeats work. If workers 0 and 1 hold bikes 2 and 5, the cheapest way to finish is the same whether worker 0 took bike 2 or bike 5: the remaining workers and remaining bikes are identical in both cases. The state that matters is the set of taken bikes, stored as an integer where bit j is set when bike j is assigned. Because workers are assigned in order, the next worker's index equals the number of set bits, so the mask alone encodes the full state.

Define solve(mask) as the minimum cost to assign all remaining workers, given that the bikes in mask are taken. This value depends only on the mask, never on how the earlier pairings were made, so memoizing it per mask is valid. That replaces a factorial-sized search tree with a table of 2^m entries, each computed at most once.

Algorithm

Example Walkthrough

For workers = [[0,0],[2,1]] and bikes = [[1,2],[3,3]], the pairwise distances are d[0][0]=3, d[0][1]=6, d[1][0]=2, d[1][1]=3. The animation follows the recursion through both branches and shows the memo table filling in.

Code

The same state space can also be processed iteratively, which removes the recursion and its function call overhead.

Intuition

Instead of recursing from the empty mask, iterate through all masks from 0 to 2^m - 1 and push costs forward. Define dp[mask] as the minimum cost to assign the bikes in mask to the first bitCount(mask) workers, with dp[0] = 0. The meaning flips relative to Approach 2: solve(mask) was the cost to finish from a state, while dp[mask] is the cost to reach it.

Iteration order is what makes this correct. Every transition goes from mask to mask | (1 << j), which is a strictly larger number, so processing masks in increasing numeric order guarantees dp[mask] holds its final value before it is used to update any successor.

Algorithm

Example Walkthrough

For workers = [[0,0],[2,1]] and bikes = [[1,2],[3,3]], m = 2, so the dp array has 2^2 = 4 entries, indexed by mask. The animation processes the masks in increasing order:

Code