4110. Разбиение на k подмножеств с равной суммой
Hard
2 решили
Дан массив
Если сумма не делится на
Числа могут быть отрицательными: элемент больше целевой суммы можно уравновесить минусами, его нельзя сразу отбрасывать. При цели 0 пустой кусок не считается: каждый из
nums и целое k. Можно ли разбить все элементы на k непустых подмножеств с одинаковой суммой? Каждый элемент ровно в одном подмножестве.Если сумма не делится на
k или k больше числа элементов — false. При k = 1 ответ всегда true (одно подмножество — весь массив).Числа могут быть отрицательными: элемент больше целевой суммы можно уравновесить минусами, его нельзя сразу отбрасывать. При цели 0 пустой кусок не считается: каждый из
k кусков должен содержать хотя бы один элемент.Примеры:
Вход:
{"nums": [4, 3, 2, 3, 5, 2, 1], "k": 4}
Выход:
true
Объяснение: nums=[4,3,2,3,5,2,1], k=4. Сумма 20 делится на 4, целевая сумма подмножества 5. Одно из разбиений: {4,1}, {3,2}, {3,2}, {5} → true.
Вход:
{"nums": [1, 2, 3, 4], "k": 3}
Выход:
false
Объяснение: nums=[1,2,3,4], k=3. Сумма 10 не делится на 3, равные суммы невозможны → false.
Вход:
{"nums": [2, 2, 2, 2], "k": 2}
Выход:
true
Объяснение: nums=[2,2,2,2], k=2. Сумма 8, цель 4. Разбиение: {2,2} и {2,2} → true.
Вход:
{"nums": [1, -1, 1, -1], "k": 2}
Выход:
true
Объяснение: Цель 0. Два куска {1,-1} и {1,-1} → true. Один элемент 1 больше цели, но его уравновешивает -1.
Ограничения:
1 <= nums.length <= 16
1 <= k <= 16
-10^4 <= nums[i] <= 10^4
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!