Проверьте, возможно ли полностью заполнить каждый контейнер одним и тем же мячом.

Имея два массива, arr[ ] C контейнеров и arr[ ] B шаров , задача состоит в том, чтобы выяснить, возможно ли полностью заполнить каждый контейнер заданными шарами, если каждый контейнер может хранить шары только одного типа. В массиве C C[i] хранится максимальное количество мячей, которое может хранить i-й контейнер. В массиве B B[i] хранится тип i-го шара.

Примеры:

Input: C = [1, 2, 3], B = [1, 2, 2, 2, 3, 3, 4, 4, 4]
Output: YES
Explanation: fill first container with ball 1, second with 2 balls with number 3 and third container with ball having number 2

Input: C = [2], B = [1, 2, 3]
Output: NO
Explanation: there’s no possible combination to fill the containers

Подход: Идея состоит в том, чтобы использовать Backtracking, чтобы проверить, возможно ли заполнить каждый контейнер или нет. Можно заметить, что нужна только частота каждого типа мячей, поэтому мы сохраняем частоту каждого типа мячей в карте . Давайте посмотрим на шаги, связанные с реализацией нашего подхода:

• Сохраняйте частоту одинаковых шаров на карте.
• Вызовите функцию getans , чтобы проверить, возможно ли заполнить контейнеры.
• Попробуйте заполнить контейнер шариками, частота которых больше, чем вместимость контейнера . Если это возможно, верните true , иначе вернитесь и проверьте другие шары.
• Если комбинации не существует, верните false .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(m^n), где n — размер arr[] C, а m — размер arr[] B.

Вспомогательное пространство: O(м)