Formatted question description: https://leetcode.ca/all/1820.html

# 1820. Maximum Number of Accepted Invitations

Medium

## Description

There are m boys and n girls in a class attending an upcoming party.

You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the i-th boy can invite the j-th girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy.

Return the maximum possible number of accepted invitations.

Example 1:

Input: grid = [[1,1,1],
[1,0,1],
[0,0,1]]

Output: 3

Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.


Example 2:

Input: grid = [[1,0,1,0],
[1,0,0,0],
[0,0,1,0],
[1,1,1,0]]

Output: 3

Explanation: The invitations are sent as follows:
- The 1st boy invites the 3rd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites no one.
- The 4th boy invites the 2nd girl.


Constraints:

• grid.length == m
• grid[i].length == n
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.

## Solution

Use backtrack. For each boy, find a girl that matches the boy, and the number of accepted invitations is added by 1 if such a match is found. Finally, return the maximum number of accepted invitations.

class Solution {
int maxInvitations = 0;

public int maximumInvitations(int[][] grid) {
int rows = grid.length, columns = grid.length;
int[] matches = new int[columns];
Arrays.fill(matches, -1);
for (int i = 0; i < rows; i++) {
boolean[] visited = new boolean[columns];
if (backtrack(grid, i, visited, matches))
maxInvitations++;
}
return maxInvitations;
}

public boolean backtrack(int[][] grid, int row, boolean[] visited, int[] matches) {
int columns = visited.length;
for (int j = 0; j < columns; j++) {
if (grid[row][j] == 1 && !visited[j]) {
visited[j] = true;
if (matches[j] == -1 || backtrack(grid, matches[j], visited, matches)) {
matches[j] = row;
return true;
}
}
}
return false;
}
}