Suma podzbioru i podział
Osiąganie celu za pomocą wybranego podzbioru
Suma podzbioru i podział to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem sumy podzbioru
Mając dane liczby i wartość docelową, należy sprawdzić, czy jakiś podzbiór daje dokładnie tę sumę. Jest to problem plecakowy, w którym wartość równa się wadze.
Logiczne DP, nie wartości
Tutaj śledzona jest osiągalność, a nie maksimum. Niech dp[s] będzie równe True, gdy jakiś podzbiór daje dokładnie sumę s.
dp = [False] * (target + 1)
dp[0] = TrueZero jest zawsze osiągalne
Pusty podzbiór daje sumę zero, więc dp[0] zaczyna z wartością True. Każda inna suma początkowo ma wartość False, dopóki jakaś liczba nie wykaże jej osiągalności.
Przejście
Dla każdej liczby należy oznaczyć s jako osiągalne, jeśli s - num było już osiągalne. Jedna liczba może ustawić True dla wielu sum.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Znowu wstecz
Każda liczba może zostać użyta co najwyżej raz, więc wewnętrzna pętla przebiega wstecz, tak jak w problemie plecakowym 0/1. Przejście w przód wykorzystałoby tę samą liczbę ponownie.
Odczytaj werdykt
Po przetworzeniu wszystkich liczb dp[target] odpowiada na pytanie. True oznacza, że istnieje poprawny podzbiór, a False — że jest to niemożliwe.
Poznaj problem podziału
Problem podziału pyta, czy można podzielić tablicę na dwie części o równych sumach. Sprowadza się on bezpośrednio do problemu sumy podzbioru.
Podziel sumę na pół
Jeśli suma całkowita jest nieparzysta, równe części są niemożliwe, więc od razu należy odpowiedzieć „nie”. W przeciwnym razie wartością docelową jest po prostu total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Wykorzystaj ponownie sumę podzbioru
Teraz wystarczy sprawdzić, czy jakiś podzbiór osiąga wartość total // 2. Jeśli jedna część osiąga cel, pozostałe elementy automatycznie tworzą pasującą drugą część.
Złożoność
Koszt wynosi rząd n razy target, czyli jest to ograniczenie pseudowielomianowe. Algorytm działa szybko, gdy target jest mały, i wolno, gdy sumy są ogromne.
Jedna rodzina problemów
Subset sum, partition i plecak 0/1 korzystają z tego samego mechanizmu. Gdy rozpoznają Państwo schemat wybierz albo pomiń, mogą ponownie użyć tej samej pętli.
Szybkie sprawdzenie
Sprawdźmy redukcję problemu partition.
Podsumowanie
Problem subset sum został rozwiązany za pomocą boolowskiego DP i pętli iterującej wstecz, a następnie problem partition sprowadzono do osiągnięcia wartości total // 2. Ten sam mechanizm, nowe zastosowania. ✅
Często zadawane pytania
Czy lekcja „Suma podzbioru i podział” jest bezpłatna?
Tak — pełny tekst „Suma podzbioru i podział” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Suma podzbioru i podział”?
Osiąganie celu za pomocą wybranego podzbioru Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Suma podzbioru i podział”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Plecak 0/1: wziąć czy zostawić
- Plecak ze zoptymalizowanym zużyciem pamięci
- Plecak bez ograniczeń i DP wydawania reszty
- Suma podzbioru i podział