Partition Equal Subset Sum: разбиение массива на две части с равной суммой
LeetCode 416 по шагам: сведение к subset sum, ДП по суммам, почему цикл идёт с конца, битсет-трюк на Python и JS, восстановление подмножества и задачи Target Sum и Last Stone Weight II.
Коротко
| Параметр | Значение |
|---|---|
| Задача | LeetCode 416: можно ли разбить массив на два подмножества с равной суммой |
| Сведение | сумма нечётная → нет; иначе ищем подмножество с суммой total / 2 |
| Состояние | dp[s] — можно ли набрать сумму s из уже просмотренных чисел |
| Переход | для каждого x: dp[s] = dp[s] or dp[s - x], s идёт от большего к меньшему |
| Сложность | по времени, по памяти, где — половина суммы |
| Битсет | сдвиг 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: перебор с мемоизацией
Для каждого числа два варианта — взять в первую часть или нет. Перебор всех вариантов — , как в задаче про подмножества. Но состояние описывается всего двумя числами: индекс i и сколько ещё осталось набрать rest. Различных состояний не больше , и их можно запомнить:
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]):
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 |
| 1 | 0, 1 |
| 5 | 0, 1, 5, 6 |
| 11 | 0, 1, 5, 6, 11 |
| 5 | 0, 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 достижима, то весь цикл — это одна операция:
Сдвиг на 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 целиком, а присваивание происходит после.
Почему это быстро? Сдвиг и | над числом из бит выполняются машинными словами по 30–64 бита за раз, и в C, а не в интерпретаторе. Асимптотика формально та же, , где — размер слова, но константа несравнимо меньше. В моём замере на 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. Одномерная динамика по сумме не работает — нужно знать, какие именно числа использованы. Решается бэктрекингом с отсечениями или ДП по маскам за при n ≤ 16.
Большие числа, мало элементов. Если чисел около 40, а сами они до , таблица по суммам не влезет. Тогда помогает meet in the middle: делим массив пополам, перебираем суммы каждой половины ( вариантов) и ищем пару, дающую 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. Почему жадность часто подводит, разобрано в статье про жадные алгоритмы. - Рекурсия без мемоизации. не дождаться.
Как это выглядит на собеседовании
LeetCode 416 — частая medium-задача на динамику, её любят за то, что в ней сразу проверяется несколько вещей:
- Видите ли вы сведение к subset sum и проверку на чётность.
- Можете ли записать состояние и переход.
- Понимаете ли, почему цикл идёт с конца, — это самый частый follow-up.
- Знаете ли про битсет или хотя бы про ранний выход.
Хороший финал ответа — назвать сложность и честно сказать, что она псевдополиномиальная: при числах до такое решение не годится, и нужен другой подход. Для тренировки возьмите размен монет (неограниченный вариант того же цикла) и Combination Sum — там те же суммы, но нужен перебор самих комбинаций.