← К задачам Режим собеседования 45:00
Обычный режим ← Предыдущая Следующая →

4110. Разбиение на k подмножеств с равной суммой

Hard 2 решили
Дан массив 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

Теги:

Массивы Backtracking

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!