Partition Equal Subset Sum: разбиение массива на две части с равной суммой

LeetCode 416 по шагам: сведение к subset sum, ДП по суммам, почему цикл идёт с конца, битсет-трюк на Python и JS, восстановление подмножества и задачи Target Sum и Last Stone Weight II.

12 мин чтенияалгоритмы · динамическое программирование · python

Коротко

ПараметрЗначение
ЗадачаLeetCode 416: можно ли разбить массив на два подмножества с равной суммой
Сведениесумма нечётная → нет; иначе ищем подмножество с суммой total / 2
Состояниеdp[s] — можно ли набрать сумму s из уже просмотренных чисел
Переходдля каждого x: dp[s] = dp[s] or dp[s - x], s идёт от большего к меньшему
СложностьO(n⋅S)O(n \cdot S) по времени, O(S)O(S) по памяти, где SS — половина суммы
Битсетсдвиг bits << x и побитовое ИЛИ — та же динамика, но в сотни раз быстрее

Это 0/1-рюкзак без стоимостей: каждое число берём не больше одного раза, и нужно ровно попасть в заданную сумму. Если вы уже знакомы с задачей о рюкзаке, половина статьи покажется знакомой; главное здесь — сведение, порядок цикла и битсет.

Постановка

Дан массив положительных чисел nums. Можно ли разбить его на две части так, чтобы суммы частей совпали?

  • [1, 5, 11, 5] → да: [11] и [1, 5, 5], по 11.
  • [1, 2, 3, 5] → нет: сумма 11 нечётная.
  • [2, 2, 3, 5] → нет: сумма 12, но набрать 6 нельзя.

Ограничения LeetCode: до 200 чисел, каждое от 1 до 100. Значит, сумма не больше 20 000, а половина — не больше 10 000. Запомните эти цифры: от них зависит, какое решение пройдёт.

Шаг 1: свести к subset sum

Если сумма всех чисел total нечётная, ответ сразу «нет». Если чётная, то разбиение существует ровно тогда, когда есть подмножество с суммой total / 2: всё остальное автоматически даст вторую половину.

Так задача превращается в классическую subset sum: есть ли подмножество с заданной суммой target. В общем виде она NP-полная, но у нас числа маленькие, и это спасает: решение будет полиномиальным по n и по величине target. Такую сложность называют псевдополиномиальной.

Ещё одна быстрая проверка: если какое-то число больше target, ответ «нет» — ему не найдётся пары.

Шаг 2: перебор с мемоизацией

Для каждого числа два варианта — взять в первую часть или нет. Перебор всех вариантов — 2n2^n, как в задаче про подмножества. Но состояние описывается всего двумя числами: индекс i и сколько ещё осталось набрать rest. Различных состояний не больше n⋅Sn \cdot S, и их можно запомнить:

from functools import lru_cache def can_partition_memo(nums: list[int]) -> bool: total = sum(nums) if total % 2: return False @lru_cache(maxsize=None) def solve(i: int, rest: int) -> bool: if rest == 0: return True if i == len(nums) or rest < 0: return False return solve(i + 1, rest - nums[i]) or solve(i + 1, rest) return solve(0, total // 2) print(can_partition_memo([1, 5, 11, 5])) # True print(can_partition_memo([2, 2, 3, 5])) # False

Рабочий вариант, но рекурсия на 200 уровней и до двух миллионов записей в кэше — не лучшая идея в Python. Переходим к таблице.

Шаг 3: таблица n × S

dp[i][s] — можно ли набрать сумму s из первых i чисел. Число x = nums[i-1] либо не берём (dp[i-1][s]), либо берём (dp[i-1][s-x]):

dp[i][s]=dp[i−1][s]∨(s≥x∧dp[i−1][s−x]),dp[0][0]=Truedp[i][s] = dp[i-1][s] \lor \big(s \ge x \land dp[i-1][s - x]\big), \qquad dp[0][0] = \text{True}
def can_partition_2d(nums: list[int]) -> bool: total = sum(nums) if total % 2: return False target = total // 2 n = len(nums) dp = [[False] * (target + 1) for _ in range(n + 1)] dp[0][0] = True for i in range(1, n + 1): x = nums[i - 1] for s in range(target + 1): dp[i][s] = dp[i - 1][s] or (s >= x and dp[i - 1][s - x]) return dp[n][target]

Пройдём [1, 5, 11, 5], target = 11. Будем выписывать множество достижимых сумм после каждого числа:

После числаДостижимые суммы (≤ 11)
—0
10, 1
50, 1, 5, 6
110, 1, 5, 6, 11
50, 1, 5, 6, 10, 11

Сумма 11 достижима уже после третьего числа — ответ «да».

Шаг 4: одна строка и цикл с конца

Строке i нужна только строка i - 1. Хочется хранить один массив и обновлять его на месте:

def can_partition(nums: list[int]) -> bool: total = sum(nums) if total % 2: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for x in nums: for s in range(target, x - 1, -1): # строго с конца! if dp[s - x]: dp[s] = True if dp[target]: return True # ранний выход return dp[target]

Почему цикл идёт от target вниз? Ячейка dp[s] читает dp[s - x] — значение левее. При обходе справа налево левые ячейки ещё не обновлены и хранят состояние «до числа x». Это и есть строка i - 1.

Если пойти слева направо, dp[s - x] к моменту чтения уже может быть обновлён этим же x — и число используется дважды. Для [2, 2, 3, 5] (target = 6) прямой цикл на числе 3 сначала отметит сумму 3, а потом из неё — сумму 6 = 3 + 3. Получится ответ «да», хотя тройка в массиве одна.

Забавно, что прямой цикл — это правильное решение другой задачи: неограниченного рюкзака, где каждое число можно брать сколько угодно раз. Так устроен размен монет. Направление цикла — единственная разница между «каждый предмет один раз» и «сколько угодно раз».

Шаг 5: битсет

Посмотрите на внутренний цикл ещё раз. Для каждого s мы делаем dp[s] |= dp[s - x]. Если представить весь массив dp как одно двоичное число, где бит s равен 1, когда сумма s достижима, то весь цикл — это одна операция:

bits∣=bits≪x\text{bits} \mathrel{|}= \text{bits} \ll x

Сдвиг на x «прибавляет x ко всем достижимым суммам сразу», а | объединяет новые суммы со старыми. В Python целые числа произвольной длины, так что получается три строки:

def can_partition_bits(nums: list[int]) -> bool: total = sum(nums) if total % 2: return False bits = 1 # бит s выставлен, если сумма s достижима; пока только 0 for x in nums: bits |= bits << x return (bits >> (total // 2)) & 1 == 1 print(can_partition_bits([1, 5, 11, 5])) # True print(can_partition_bits([1, 2, 3, 5])) # False

Проблема «не использовать число дважды» здесь не возникает вовсе: сдвиг берёт старое значение bits целиком, а присваивание происходит после.

Почему это быстро? Сдвиг и | над числом из SS бит выполняются машинными словами по 30–64 бита за раз, и в C, а не в интерпретаторе. Асимптотика формально та же, O(n⋅S/w)O(n \cdot S / w), где ww — размер слова, но константа несравнимо меньше. В моём замере на 200 числах до 100 обычная одномерная динамика работала около 100 мс, двумерная — около 250 мс, битсет — доли миллисекунды. В C++ то же самое делается через std::bitset<10001>, и это стандартный приём на олимпиадах. Больше про операции с битами — в статье про битовые манипуляции.

На JavaScript работает BigInt:

function canPartitionBits(nums) { const total = nums.reduce((a, b) => a + b, 0) if (total % 2) return false let bits = 1n for (const x of nums) bits |= bits << BigInt(x) return ((bits >> BigInt(total / 2)) & 1n) === 1n } console.log(canPartitionBits([1, 5, 11, 5])) // true console.log(canPartitionBits([1, 2, 3, 5])) // false

Обычную динамику на JS удобно писать на Uint8Array — та же логика, что и в Python:

function canPartition(nums) { const total = nums.reduce((a, b) => a + b, 0) if (total % 2) return false const target = total / 2 const dp = new Uint8Array(target + 1) dp[0] = 1 for (const x of nums) { for (let s = target; s >= x; s--) { if (dp[s - x]) dp[s] = 1 } } return dp[target] === 1 }

На собеседовании начинайте с обычной динамики, а битсет предлагайте как оптимизацию. Если вы сразу напишете три строки со сдвигом, интервьюер всё равно попросит объяснить, почему это работает, — то есть рассказать про динамику.

Восстановить само разбиение

Если нужно не «да/нет», а сами подмножества, понадобится двумерная таблица. Идём с конца: если сумму s можно набрать без числа i, значит, оно не обязательно; если нельзя — берём его.

def find_partition(nums: list[int]) -> list[int] | None: total = sum(nums) if total % 2: return None target = total // 2 n = len(nums) dp = [[False] * (target + 1) for _ in range(n + 1)] dp[0][0] = True for i in range(1, n + 1): x = nums[i - 1] for s in range(target + 1): dp[i][s] = dp[i - 1][s] or (s >= x and dp[i - 1][s - x]) if not dp[n][target]: return None picked, s = [], target for i in range(n, 0, -1): if not dp[i - 1][s]: # без nums[i-1] сумму s не собрать — берём его picked.append(nums[i - 1]) s -= nums[i - 1] return picked print(find_partition([1, 5, 11, 5])) # [11] print(find_partition([3, 3, 3, 4, 5])) # [3, 3, 3]

Все пять версий — мемоизацию, две таблицы, битсет и вариант с множеством сумм — я сверил между собой на трёх тысячах случайных массивов.

Родственные задачи

494. Target Sum. Перед каждым числом поставить + или -, чтобы получилось target. Пусть P — сумма чисел с плюсом, N — с минусом. Тогда P - N = target и P + N = total, откуда P = (total + target) / 2. Задача свелась к подсчёту подмножеств с суммой P — тот же цикл с конца, только вместо | сложение:

def find_target_sum_ways(nums: list[int], target: int) -> int: total = sum(nums) if abs(target) > total or (total + target) % 2: return 0 goal = (total + target) // 2 # сумма чисел со знаком плюс ways = [0] * (goal + 1) ways[0] = 1 for x in nums: for s in range(goal, x - 1, -1): ways[s] += ways[s - x] return ways[goal] print(find_target_sum_ways([1, 1, 1, 1, 1], 3)) # 5

1049. Last Stone Weight II. Камни попарно сталкиваются, нужно минимизировать остаток. После раскрытия скобок это опять разбиение на две группы, только теперь не точное: ищем достижимую сумму s ≤ total / 2, максимально близкую к половине, ответ total - 2s. Битсет даёт все достижимые суммы разом:

def last_stone_weight_ii(stones: list[int]) -> int: total = sum(stones) bits = 1 for x in stones: bits |= bits << x for s in range(total // 2, -1, -1): if bits >> s & 1: return total - 2 * s print(last_stone_weight_ii([2, 7, 4, 1, 8, 1])) # 1

698. Partition to K Equal Sum Subsets. Уже не две части, а k. Одномерная динамика по сумме не работает — нужно знать, какие именно числа использованы. Решается бэктрекингом с отсечениями или ДП по маскам за O(2n⋅n)O(2^n \cdot n) при n ≤ 16.

Большие числа, мало элементов. Если чисел около 40, а сами они до 10910^9, таблица по суммам не влезет. Тогда помогает meet in the middle: делим массив пополам, перебираем суммы каждой половины (2202^{20} вариантов) и ищем пару, дающую target.

Типичные ошибки

  • Забыть проверку на нечётность. total // 2 молча округлит вниз, и для [1, 2] код начнёт искать сумму 1 — и найдёт её.
  • Прямой порядок во внутреннем цикле. Число используется несколько раз. Тест-ловушка: [2, 2, 3, 5] должен дать False.
  • Таблица размера total, а не total / 2. Работает, но вдвое медленнее и съедает вдвое больше памяти.
  • Жадность. Сортировать по убыванию и раскладывать в меньшую кучку — эвристика, а не решение. На [3, 3, 2, 2, 2] она кладёт обе тройки в разные кучки и в итоге получает 7 и 5, хотя [3, 3] и [2, 2, 2] дают ровно по 6. Почему жадность часто подводит, разобрано в статье про жадные алгоритмы.
  • Рекурсия без мемоизации. 22002^{200} не дождаться.

Как это выглядит на собеседовании

LeetCode 416 — частая medium-задача на динамику, её любят за то, что в ней сразу проверяется несколько вещей:

  1. Видите ли вы сведение к subset sum и проверку на чётность.
  2. Можете ли записать состояние и переход.
  3. Понимаете ли, почему цикл идёт с конца, — это самый частый follow-up.
  4. Знаете ли про битсет или хотя бы про ранний выход.

Хороший финал ответа — назвать сложность O(n⋅S)O(n \cdot S) и честно сказать, что она псевдополиномиальная: при числах до 10910^9 такое решение не годится, и нужен другой подход. Для тренировки возьмите размен монет (неограниченный вариант того же цикла) и Combination Sum — там те же суммы, но нужен перебор самих комбинаций.

Потренироваться в спокойной обстановке

Все задачи