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

# 1820. Maximum Number of Accepted Invitations

## Level

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[0].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;
}
}
```