Partition Equal Subset Sum

Начните с общей суммы. Если она нечётная, разбить числа на две равные группы нельзя, потому что сумма двух одинаковых целых чисел чётная. Иначе сумма каждой группы должна быть ровно target = total / 2. Как только вы найдёте значения, сумма которых равна target, значения, которые вы не выбрали, сами составят вторую половину. Поэтому достаточно ответить на один вопрос: существует ли подмножество с суммой target?

Рассматривайте значения по порядку и выбирайте для каждого одно из двух: поместить его в первую группу или оставить для второй. Вспомогательная функция reach(i, remaining) проверяет, можно ли составить сумму remaining из значений, начиная с индекса i. Она возвращает true, когда remaining становится равным 0, false, когда значения заканчиваются или remaining становится меньше 0; в противном случае она пробует оба варианта для nums[i].

Каждое подмножество соответствует одному пути выбора, поэтому поиск не может пропустить разбиение и даёт правильный ответ. Он работает медленно, потому что существует 2^n путей, а для входных данных, которые нельзя разбить, приходится пробовать почти все из них. Возьмём 199 копий числа 100 и одно число 98: общая сумма равна 19998, сумма 9999 никогда не достигается, и поиск пробует все способы выбрать не более 99 чисел 100 — около 4 × 10^59 путей. Даже для 40 значений получается 2^40, то есть около 10^12 путей.

Рекурсия снова и снова задаёт один и тот же вопрос. reach(i, remaining) зависит только от двух чисел: i от 0 до n и remaining от 0 до target. Значит, существует не более (n+1) × (target+1) разных вопросов — на граничных значениях это примерно 201 × 10001 ≈ 2 × 10^6, достаточно мало, чтобы ответить на каждый из них один раз.

Вычислим ответы вперёд, заполняя таблицу. can[i][s] показывает, можно ли получить сумму s из некоторых первых i значений. Если значений нет, возможна только сумма 0, поэтому в строке 0 везде false, кроме can[0][0]. Значение num = nums[i-1] даёт два способа получить s: не брать num, значит, предыдущие значения уже дают s, или взять его, значит, предыдущие значения дают s-num. Вот и всё правило: can[i][s] = can[i-1][s] or can[i-1][s-num], причём вторая часть учитывается только при s ≥ num. Каждая строка читает данные только из строки выше, поэтому каждое значение используется не более одного раза.

Для [6, 1, 4, 9, 2] при target 11 множество достижимых сумм растёт от {0} до {0, 6}, затем до {0, 1, 6, 7}, а затем до {0, 1, 4, 5, 6, 7, 10, 11}. Сумма 11 появляется после добавления 4 (6 + 1 + 4), и сохраняется в последующих строках. Ответ — can[n][target]. На каждую ячейку требуется постоянное количество операций, поэтому временная сложность и объём памяти составляют O(n × target).

Каждая строка таблицы считывает только строку над ней, поэтому достаточно одной строки, если обновлять её на месте: reach[s] показывает, дают ли некоторые из уже просмотренных значений в сумме s. Опасность заключается в порядке обновлений. Если перебирать s по возрастанию, значение reach[s-num] уже могло стать true из-за того же num. Для [3, 9] и целевого значения 6 число 3 отмечает reach[3], а затем считывает его и отмечает reach[6], как будто у тебя было две тройки, и алгоритм выдаёт true для несуществующего разбиения.

Перебирай s по убыванию, от target до num. Тогда s-num — меньший индекс, которого это значение ещё не затронуло, поэтому reach[s-num] по-прежнему хранит ответ, который был до появления num. Это в точности can[i-1][s-num] из таблицы, и одна строка выполняет работу всей таблицы.

Можно также остановиться, как только reach[target] станет true, потому что последующие значения только добавляют достижимые суммы и никогда не удаляют их. В худшем случае по-прежнему потребуется O(n × target) шагов, примерно 2 × 10^6, а объём памяти сократится до target + 1 булевых значений.