Partition Equal Subset Sum

Zacznij od obliczenia sumy. Jeśli jest nieparzysta, podział nie jest możliwy, ponieważ suma dwóch równych liczb całkowitych jest parzysta. W przeciwnym razie każda grupa musi mieć sumę równą dokładnie target = total / 2. Gdy znajdziesz wartości, które dają target, niewybrane wartości same utworzą drugą połowę. Wystarczy więc odpowiedzieć na jedno pytanie: czy istnieje podzbiór, którego suma wynosi target?

Przejdź po kolei przez wartości i dla każdej podejmij jedną decyzję: dodaj ją do pierwszej grupy albo zostaw ją dla drugiej. Funkcja pomocnicza reach(i, remaining) odpowiada na pytanie, czy wartości od indeksu i wzwyż mogą dać sumę remaining. Zwraca true, gdy remaining osiąga 0, false, gdy kończą się wartości lub suma spada poniżej 0, a w przeciwnym razie sprawdza obie możliwości dla nums[i].

Każdy podzbiór odpowiada jednej ścieżce wyborów, więc wyszukiwanie nie może przeoczyć podziału i daje poprawną odpowiedź. Jest powolne, ponieważ istnieje 2^n ścieżek, a dane wejściowe, dla których podział nie istnieje, zmuszają je do sprawdzenia niemal wszystkich. Weź 199 kopii liczby 100 i jedną liczbę 98: suma wynosi 19998, suma docelowa 9999 nigdy nie zostaje osiągnięta, a wyszukiwanie sprawdza każdy sposób wybrania najwyżej 99 setek — około 4 × 10^59 ścieżek. Nawet 40 wartości daje 2^40, czyli około 10^12 ścieżek.

Rekurencja zadaje wciąż to samo pytanie. reach(i, remaining) zależy tylko od dwóch liczb: i od 0 do n oraz remaining od 0 do target. Oznacza to co najwyżej (n+1) × (target+1) różnych pytań, czyli około 201 × 10001 ≈ 2 × 10^6 przy wartościach granicznych — wystarczająco mało, by odpowiedzieć na każde z nich tylko raz.

Zbuduj odpowiedzi w tabeli, zaczynając od początku. can[i][s] informuje, czy pewne wartości spośród pierwszych i sumują się do s. Bez żadnych wartości możliwa jest tylko suma 0, więc wiersz 0 zawiera false, z wyjątkiem can[0][0]. Wartość num = nums[i-1] daje dwa sposoby uzyskania s: pominąć num, czyli wcześniejsze wartości już sumują się do s, albo ją dodać, czyli wcześniejsze wartości sumują się do s-num. To cała reguła: can[i][s] = can[i-1][s] or can[i-1][s-num], przy czym druga część ma znaczenie tylko wtedy, gdy s ≥ num. Każdy wiersz odczytuje dane tylko z wiersza powyżej, więc każda wartość jest używana co najwyżej raz.

Dla [6, 1, 4, 9, 2] i celu 11 osiągalne sumy zwiększają się od {0} do {0, 6}, następnie do {0, 1, 6, 7}, a potem do {0, 1, 4, 5, 6, 7, 10, 11}. Suma 11 pojawia się po dodaniu 4 (6 + 1 + 4), a kolejne wiersze ją zachowują. Odpowiedzią jest can[n][target]. Każda komórka wymaga stałej liczby operacji, więc zarówno czas, jak i pamięć mają złożoność O(n × target).

Każdy wiersz tabeli odczytuje tylko wiersz powyżej, więc wystarczy jeden wiersz, jeśli aktualizujesz go w miejscu: reach[s] informuje, czy niektóre z dotychczasowych wartości sumują się do s. Niebezpieczna jest kolejność aktualizacji. Jeśli przechodzisz po s rosnąco, reach[s-num] mogło już zostać ustawione przez tę samą wartość num. Dla [3, 9] i celu 6 wartość 3 oznacza reach[3], a następnie odczytuje tę wartość, by oznaczyć reach[6], tak jakby dostępne były dwie trójki, i zwracasz true dla podziału, który nie istnieje.

Przechodź po s malejąco, od target do num. Wtedy s-num jest mniejszym indeksem, którego ta wartość jeszcze nie zmieniła, więc reach[s-num] nadal zawiera odpowiedź sprzed pojawienia się num. To dokładnie can[i-1][s-num] z tabeli, a pojedynczy wiersz wykonuje pracę całej tabeli.

Możesz też zatrzymać się, gdy tylko reach[target] stanie się true, ponieważ kolejne wartości tylko dodają osiągalne sumy i nigdy żadnej nie usuwają. W najgorszym przypadku nadal potrzeba O(n × target) kroków, czyli około 2 × 10^6, a ilość pamięci spada do target + 1 wartości logicznych.