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

Дан непустой массив положительных целых чисел nums. Определите, можно ли разбить его на два подмножества с равными суммами. Например, массив [1, 5, 11, 5] можно разделить на [1, 5, 5] и [11] — сумма каждого подмножества равна 11. Если общая сумма нечётна, ответом сразу будет False. В противном случае нужно найти подмножество с суммой total_sum // 2 — это классическая задача о сумме подмножества.

Ключевое сведение: если общая сумма S чётна и существует подмножество с суммой S//2, оставшиеся элементы автоматически также дают сумму S//2. Итак, задача о равном разбиении на подмножества сводится к вопросу: существует ли подмножество чисел с суммой S//2? Это классическая NP-полная задача о сумме подмножеств, которую мы решаем с помощью динамического программирования по схеме задачи о рюкзаке 0/1 за время O(n × S).

Определим логический массив dp[c], где dp[c] = True означает, что существует подмножество с суммой ровно c. Инициализируйте dp[0] = True (сумма пустого подмножества равна 0), а все остальные элементы — значением False. Для каждого числа num перебирайте вместимость от target до num (обратный перебор в задаче о рюкзаке 0/1) и задавайте dp[c] = dp[c] or dp[c - num].

Для [1, 5, 11, 5] общая сумма = 22, целевая сумма = 11. Изначально dp[0]=True. После обработки числа 1: dp[1]=True. После обработки числа 5: dp[5]=True, dp[6]=True. После обработки числа 11: dp[11]=True (используется только само число 11). Мы уже получили dp[11]=True, но продолжаем обрабатывать все числа. Итоговый ответ: dp[11]=True, поэтому разбиение возможно.

Можно досрочно завершить вычисления: если dp[target] в какой-то момент становится равным True, немедленно верните True. Это может существенно ускорить выполнение в наилучшем случае. Кроме того, если отдельный элемент равен target, можно сразу вернуть True. Если отдельный элемент превышает target, он не может входить в подмножество с целевой суммой, но остальные элементы всё равно нужно проверить.

Другой вариант — поддерживать множество достижимых сумм. Начните с {0}. Для каждого числа добавляйте его к каждой сумме из текущего множества: reachable = reachable | {s + num for s in reachable}. Оставляйте только суммы, не превышающие целевую. В конце проверьте, содержится ли target в множестве. Этот подход интуитивно понятен, но может потребовать больше памяти и на практике оказаться медленнее.

Подход с DP работает за время O(n × S), где S = sum(nums), и использует O(S) памяти для логического массива. При ограничениях LeetCode (n ≤ 200, сумма ≤ 20 000) это не более 4 000 000 операций — очень быстро. Подход с множеством имеет такую же асимптотическую сложность, но на практике может быть медленнее из-за затрат на создание множеств.

Рассмотрим связанную задачу: подсчитать количество подмножеств с суммой, равной целевой. Замените логическое значение в DP на целое число: dp[c] = number of ways to reach sum c. Используйте сложение вместо OR: dp[c] += dp[c - num]. Инициализируйте dp[0] = 1. Обратный перебор остаётся тем же. Это обобщение показывает, как шаблон задачи о рюкзаке адаптируется к разным вопросам о подмножествах.

Будьте готовы к дополнительным вопросам: (1) Что делать, если нужно вернуть само разбиение? — потребуется двумерный DP для восстановления решения. (2) Что делать, если элементы могут быть отрицательными? — сдвиньте целевую сумму или используйте словарь вместо массива. (3) Какова временная сложность? — O(n × сумма). (4) Можно ли улучшить решение, если многие числа одинаковы? — да, используйте подсчёт частот, чтобы уменьшить количество внешних итераций. Всегда заранее упоминайте эти компромиссы.

Задача о равном разбиении на подмножества — это прямое применение задачи о рюкзаке 0/1: предметами являются числа, их веса равны значениям, а вместимость рюкзака равна целевой сумме. Мы проверяем, равна ли максимальная ценность целевой сумме (то есть проверяем существование решения), а не ищем саму максимальную ценность. Обратный перебор выполняется так же, меняется только операция: вместо max используется логическое or. Распознавание этой связи на собеседовании демонстрирует развитое умение находить закономерности.

Обработайте следующие граничные случаи: (1) массив длины 1 — один элемент нельзя разделить, поэтому результат всегда False; (2) все элементы одинаковы, а их количество чётно — решение может существовать или отсутствовать в зависимости от значений элементов; (3) очень большие суммы — проверьте ограничения перед выделением массива DP; (4) элементы, превышающие целевую сумму, можно пропустить, поскольку они никогда не войдут в подмножество с такой суммой. Проверка максимального элемента в качестве досрочного завершения эффективно обрабатывает случай (4).

Проверьте, насколько вы усвоили концепции структур данных и алгоритмов — подготовки к собеседованию по программированию, рассмотренные в этом уроке.

В этом уроке вы узнали: задача о равном разбиении на подмножества сводится к задаче о сумме подмножеств с целевой суммой, равной общей сумме // 2, одномерный логический DP dp[c] использует обратный перебор, как и задача о рюкзаке 0/1, а подход обобщается на подсчёт подмножеств заменой логического OR на сложение целых чисел. Далее мы перейдём к задаче о целевой сумме, преобразуя присваивание знаков в задачу о рюкзаке на разности сумм подмножеств.