Перестановки одинаковой суммы (сумма подпоследовательностей)
Hard
Дан массив
Каждый элемент используется ровно в одном подмножестве. Если суммарное значение массива не делится на
nums и целое k. Можно ли разбить все элементы на k непустых подмножеств с одинаковой суммой?Каждый элемент используется ровно в одном подмножестве. Если суммарное значение массива не делится на
k, такое разбиение невозможно. Верните true или false.Примеры:
Вход:
{"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.
Ограничения:
1 <= n <= 16; 1 <= k <= n; -10^4 <= nums[i] <= 10^4 (малые n, перебор допустим)
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!