Exhibition Opponent Cards

All perfect matchings within a cost budget in a weighted graph

MediumBacktrackingPerfect MatchingsMemoization

A football league is arranging a single exhibition day. Every club must play exactly one other club, and no club may appear in two matches.

Clubs are numbered from 0 to n - 1, where n is the number of rows in fees. For two different clubs i and j:

  • fees[i][j] == -1 means they cannot play each other.
  • Otherwise, fees[i][j] is the cost of arranging their match.

Return every possible match card whose total cost is at most budget.

Represent each card as a flat list [a0, b0, a1, b1, ...]. Within every pair, the smaller club number must come first. Order the pairs by their smaller club numbers. Return the cards in lexicographically increasing order, with no duplicates.

If no card is possible, return an empty list. If there are no clubs, the one valid card is the empty card, so return [[]].

Examples

Example 1

Input: fees = [[-1,2,3,4],[2,-1,4,3],[3,4,-1,2],[4,3,2,-1]], budget = 6
Output: [[0,1,2,3],[0,2,1,3]]

There are three possible ways to pair four clubs before considering costs. Pairing 0 with 1 and 2 with 3 costs 4; pairing 0 with 2 and 1 with 3 costs 6; pairing 0 with 3 and 1 with 2 costs 8. Only the first two cards fit the budget.

Example 2

Input: fees = [[-1,-1,1,5],[-1,-1,5,1],[1,5,-1,2],[5,1,2,-1]], budget = 3
Output: [[0,2,1,3]]

Clubs 0 and 1 cannot meet. Of the other two complete pairings, only the one pairing 0 with 2 and 1 with 3 fits the budget.

Example 3

Input: fees = [], budget = 0
Output: [[]]

With no clubs, no matches are required. The empty card has cost zero and is valid.

Constraints

  • n = fees.length is even and 0 <= n <= 12.
  • fees is an n by n matrix.
  • fees[i][i] == -1.
  • fees[i][j] == fees[j][i].
  • Every fee is either -1 or an integer from 0 through 1,000,000.
  • 0 <= budget <= 6,000,000.

The required ordering is the usual lexicographic ordering of integer lists. With P valid cards, the reference uses O(n^2 * 2^n + n^2 * P) time and O(2^n + n) auxiliary space, excluding the O(n * P) output storage. Enumeration is performed by backtracking; memoization supplies a feasibility bound.

Hints

Show hint 1

At each step, pair the smallest club that has not yet been used. This avoids generating the same card in different match orders.

Show hint 2

Memoize the minimum cost of completely pairing each remaining-club bitmask. Use that cost to reject branches that cannot finish within the budget.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you return only the lexicographically first valid card without constructing all valid cards?
  • How would you change the implementation to stream valid cards one at a time?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem