Podział na równe sumy podzbiorów

Mając niepustą tablicę dodatnich liczb całkowitych nums, należy ustalić, czy można podzielić ją na dwa podzbiory o równych sumach. Na przykład [1, 5, 11, 5] można podzielić na [1, 5, 5] i [11], przy czym suma obu podzbiorów wynosi 11. Jeśli suma całkowita jest nieparzysta, odpowiedź od razu wynosi False. W przeciwnym razie musimy znaleźć podzbiór o sumie równej total_sum // 2 — jest to klasyczny problem sumy podzbioru.

Kluczowa redukcja: jeśli łączna suma S jest parzysta, a suma pewnego podzbioru wynosi S//2, to pozostałe elementy również automatycznie sumują się do S//2. Zatem problem Partition Equal Subset Sum sprowadza się do pytania: czy istnieje podzbiór nums o sumie S//2? Jest to klasyczny NP-zupełny problem Subset Sum, który rozwiązujemy za pomocą programowania dynamicznego dla problemu plecakowego 0/1 w czasie O(n × S).

Należy zdefiniować tablicę wartości logicznych dp[c], gdzie dp[c] = True oznacza, że istnieje podzbiór o sumie dokładnie c. Należy zainicjalizować dp[0] = True (suma pustego podzbioru wynosi 0), a wszystkie pozostałe wartości ustawić na False. Dla każdej liczby num należy iterować po pojemności od target w dół do num (iteracja wsteczna jak w problemie plecakowym 0/1) i ustawić dp[c] = dp[c] or dp[c - num].

Dla [1, 5, 11, 5], total=22, target=11. Początkowo dp[0]=True. Po num=1: dp[1]=True. Po num=5: dp[5]=True, dp[6]=True. Po num=11: dp[11]=True (z wykorzystaniem samej liczby 11). Wartość dp[11]=True została już znaleziona, ale nadal przetwarzamy wszystkie liczby. Wynik końcowy: dp[11]=True, więc podział jest możliwy.

Można dodać wcześniejsze zakończenie: jeśli w dowolnym momencie dp[target] stanie się równe True, należy natychmiast zwrócić True. Może to znacznie przyspieszyć działanie w najlepszym przypadku. Jeśli pojedynczy element jest równy target, również można od razu zwrócić True. Jeśli pojedynczy element przekracza target, nie może należeć do żadnego podzbioru o sumie równej target, ale nadal trzeba sprawdzić pozostałe elementy.

Alternatywnym rozwiązaniem jest utrzymywanie zbioru osiągalnych sum. Należy rozpocząć od {0}. Dla każdej liczby należy dodać ją do każdej sumy znajdującej się w bieżącym zbiorze: reachable = reachable | {s + num for s in reachable}. Następnie należy odfiltrować sumy, które przekraczają target. Na końcu sprawdzamy, czy target znajduje się w zbiorze. To podejście jest intuicyjne, ale może wymagać więcej pamięci i w praktyce działać wolniej.

Podejście DP działa w czasie O(n × S), gdzie S = sum(nums), i wykorzystuje O(S) pamięci na tablicę wartości logicznych. Dla ograniczeń z LeetCode (n ≤ 200, sum ≤ 20,000) oznacza to najwyżej 4 000 000 operacji — bardzo szybko. Podejście ze zbiorem ma taką samą złożoność asymptotyczną, ale w praktyce może działać wolniej ze względu na koszt tworzenia zbiorów.

Pokrewny problem polega na zliczeniu podzbiorów, których suma jest równa target. Należy zmienić typ DP z wartości logicznych na liczby całkowite: dp[c] = number of ways to reach sum c. Zamiast operatora OR należy użyć dodawania: dp[c] += dp[c - num]. Należy zainicjalizować dp[0] = 1. Iteracja wsteczna pozostaje taka sama. To uogólnienie pokazuje, jak szablon problemu plecakowego można dostosować do różnych pytań dotyczących podzbiorów.

Należy spodziewać się pytań uzupełniających: (1) Co zrobić, jeśli trzeba zwrócić rzeczywisty podział? — wymaga to użycia DP 2D do odtworzenia rozwiązania. (2) Co zrobić, jeśli elementy mogą być ujemne? — należy przesunąć target albo użyć słownika zamiast tablicy. (3) Jaka jest złożoność czasowa? — O(n × sum). (4) Czy można poprawić rozwiązanie, jeśli wiele liczb jest takich samych? — tak, można użyć zliczania częstotliwości, aby zmniejszyć liczbę iteracji zewnętrznych. Należy samodzielnie wspomnieć o tych kompromisach.

Partition Equal Subset Sum jest bezpośrednim zastosowaniem problemu plecakowego 0/1: elementami są liczby, ich wagi są równe wartościom, a pojemność plecaka jest równa target. Pytamy, czy maksymalna wartość jest równa target (sprawdzamy wykonalność), a nie jaka jest sama maksymalna wartość. Iteracja wsteczna pozostaje taka sama — zmienia się jedynie operacja z max na logiczne or. Rozpoznanie tego powiązania podczas rozmowy rekrutacyjnej świadczy o dobrej umiejętności rozpoznawania wzorców.

Należy obsłużyć następujące przypadki brzegowe: (1) tablica długości 1 — pojedynczego elementu nie można podzielić, więc wynik to zawsze False; (2) wszystkie elementy są identyczne, a ich liczba jest parzysta — rozwiązanie może istnieć lub nie, zależnie od wartości pojedynczych elementów; (3) bardzo duże sumy — przed zaalokowaniem tablicy DP należy sprawdzić ograniczenia; (4) elementy większe od target — można je pominąć, ponieważ nigdy nie mogą należeć do podzbioru o sumie równej target. Sprawdzenie największego elementu jako warunek wcześniejszego zakończenia skutecznie obsługuje przypadek (4).

Sprawdź swoje rozumienie zagadnień z zakresu Data Structures & Algorithms — Coding Interview Prep przedstawionych w tej lekcji.

W tej lekcji poznali Państwo następujące zagadnienia: Partition Equal Subset Sum sprowadza się do problemu sumy podzbioru z target = total//2, jednowymiarowe DP z wartościami logicznymi dp[c] wykorzystuje iterację wsteczną identyczną jak w problemie plecakowym 0/1 oraz podejście można uogólnić na zliczanie podzbiorów, zastępując logiczne OR dodawaniem liczb całkowitych. Następnie zajmiemy się problemem Target Sum, przekształcając przypisywanie znaków w problem plecakowy oparty na różnicy sum podzbiorów.