Разделение массива на K подмассивов с уникальными суммами
Hard
Дан массив
Верните
nums и число k. Можно ли разрезать массив на ровно k непустых непрерывных кусков (идущих подряд по индексам) так, чтобы суммы этих кусков были попарно различны?Верните
true или false. Порядок кусков фиксирован слева направо: это разбиение массива на смежные отрезки, а не произвольные подмножества.Примеры:
Вход:
{"nums": [1, 2, 3, 4, 5], "k": 3}
Выход:
true
Объяснение: nums=[1,2,3,4,5], k=3. Один из подходящих разрезов: [1] | [2,3] | [4,5] со суммами 1, 5 и 9 — все разные → true.
Вход:
{"nums": [1, 2, 3, 4], "k": 2}
Выход:
true
Объяснение: nums=[1,2,3,4], k=2. Например, [1,2] | [3,4] со суммами 3 и 7 — различны → true.
Вход:
{"nums": [1, 1, 1, 1, 1], "k": 3}
Выход:
false
Объяснение: nums=[1,1,1,1,1], k=3. Все элементы равны 1, поэтому сумма куска равна только его длине. Нужны три положительные длины с попарно разными суммами (длинами), в сумме дающие 5. Такого тройки длин не существует → false.
Ограничения:
1 <= nums.length <= 20
1 <= nums[i] <= 1000
1 <= k <= nums.length
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!