Разбиение массива целых чисел на K подмножеств с равными суммами — метод обратного поиска

Бесплатный 5-дневный мини-курс:
Попробуйте нашу полную платформу:
📹 Интуитивно понятные видеообъяснения 🏃 Запускайте код по мере обучения 💾 Сохраняйте прогресс ❓Новые, ещё не просмотренные вопросы 🔎 Получить все решения Вопрос: Дан массив целых чисел nums и положительное целое число k. Найдите, можно ли разделить этот массив на k непустых подмножеств, суммы которых равны. Пример: Входные данные: nums = [4, 3, 2, 3, 5, 2, 1] k = 4 Выходные данные: true Объяснение: Можно разделить его на 4 подмножества (5), (1, 4), (2, 3), (2, 3) с равными суммами. Итак, мы возьмём наш исходный массив и попробуем сформировать k блоков, где: Пусть «sum» будет суммой всех элементов массива. Каждый блок имеет сумму, равную сумме / k (то есть, мы берём сумму всего массива и делаем каждый блок равным отрезком этой общей кумулятивной суммы... отсюда и «K ПОДМНОЖЕСТВ С РАВНЫМИ СУММАМИ»). Проверка Это невозможно, если: k равно 0 или меньше. sum % k не равно 0 (то есть общая сумма массива не позволяет нам иметь k блоков с равными суммами... мы работаем только с целыми числами). Пояснение кода Функция драйвера: Мы получаем сумму числа для проверки того, что мы можем иметь k блоков с равными суммами без нецелых сумм в каждом блоке. k также не может быть меньше или равно 0. Если все проверки пройдены, мы переходим к рекурсии. Рекурсия: Наш подход здесь будет заключаться в заполнении каждой группы уникальными элементами, никогда не помещая элемент более чем в одну группу. Каждый кадр рекурсии проходит через цикл и пытается поместить элемент, который ещё не был помещен в группу (мы отслеживаем размещенные элементы), а затем рекурсия выполняется с этим элементом. Вот почему мы увеличиваем начальное значение на 1: мы используем только элементы, следующие за только что выбранным. Мы также добавляем значение этого элемента к нашей рабочей сумме. После заполнения группы мы продолжим рекурсию, сохраняя использованные элементы как просмотренные, и устанавливаем начальное значение равным 0, поскольку весь массив снова доступен для использования, если элемент ещё не был использован. Рабочая сумма устанавливается равной 0, поскольку мы работаем с новой группой. ПОСЛЕ ЗАПОЛНЕНИЯ K - 1 ГРУППЫ МЫ ЗАВЕРШАЕМ РАБОТУ. Это связано с тем, что если мы заполнили k - 1 контейнер, последний контейнер ДОЛЖЕН быть заполненным, так как сумма % k == 0. Поскольку мы могли бы заполнить все остальные контейнеры до этого момента поровну, мы точно знаем, что сможем завершить последний контейнер без переполнения или недооценки. Сложности Мне потребовалось 3 часа размышлений, и я так и не смог определить сложность хранилища настолько, чтобы я мог ЧЕТКО объяснить заданную верхнюю границу времени. Никто на Leetcode не уверен, а модераторы, как всегда, дают очень туманные объяснения. Оставлю это в покое. Время: O( ? ) Место: O( n ) Булев массив для обозначения использованных элементов автоматически занимает O(n) места. Кроме того, мы разместим почти n элементов, поэтому стек вызовов будет расти линейно с размером входных данных, но это вопрос второстепенный. Булев массив занимает O(n) места, по крайней мере, с самого начала. ++++++++++++++++++++++++++++++++++++++++++++++++++++ HackerRank:    / @hackerrankofficial   Тушар Рой:    / tusharroy2525   GeeksForGeeks:    / @geeksforgeeksvideos   Джарвис Джонсон:    / vsympathyv   Успех в технологиях:    / @successintech