Suma docelowa ze znakami dodatnimi i ujemnymi
Przekształcać problem przypisywania znaków w problem plecakowy oparty na różnicy sum podzbiorów i rozwiązywać go w czasie O(n × sum)
Suma docelowa ze znakami dodatnimi i ujemnymi to bezpłatna lekcja DSA 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem Target Sum
Dla tablicy liczb całkowitych nums oraz liczby całkowitej target należy przypisać każdej liczbie znak + lub -, tak aby wynik wyrażenia był równy target. Należy zwrócić liczbę różnych sposobów wykonania tego zadania. Na przykład dla nums=[1,1,1,1,1] i target=3 istnieje 5 sposobów (można wybrać 4 elementy, którym zostanie przypisany znak plus, oraz 1 element ze znakiem minus, przy czym pozycje tych elementów mogą się różnić).
Brute force: wyliczanie DFS
Podejście DFS przypisuje każdej liczbie znak + albo - i wykonuje rekurencję, zwracając liczbę węzłów liści, dla których osiągnięto target. Jest ono poprawne, ale ma złożoność czasową O(2^n) — wykładniczą. Dla n=20 oznacza to ponad milion wywołań rekurencyjnych. Warto najpierw wspomnieć o podejściu DFS, a następnie szybko przejść do optymalizacji za pomocą DP.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5DFS z memoizacją
Do DFS należy dodać memoizację: stan opisuje para (index, current_sum). Ponieważ current_sum może przyjmować wartości od -total do +total, istnieje O(n × total) unikatowych stanów. Dzięki memoizacji DFS działa w czasie i przestrzeni O(n × total). To rozwiązanie sprawdza się podczas rozmów rekrutacyjnych, ale DP oparte na przekształceniu jest bardziej eleganckie i oszczędniejsze pamięciowo.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Przekształcenie matematyczne
Niech P będzie zbiorem liczb, którym przypisano znak +, a N zbiorem liczb, którym przypisano znak -. Wtedy: sum(P) - sum(N) = target oraz sum(P) + sum(N) = total. Po dodaniu równań otrzymujemy: 2 × sum(P) = target + total, a więc sum(P) = (target + total) / 2. Problem sprowadza się do: zliczenia podzbiorów nums o sumie (target + total) / 2. Jest to dokładnie wariant problemu plecakowego 0/1 polegający na zliczaniu podzbiorów.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')Sprawdzanie poprawności przed DP
Przed uruchomieniem DP należy sprawdzić: (1) target + total musi być parzyste (w przeciwnym razie sum(P) nie jest liczbą całkowitą, więc rozwiązanie nie istnieje); (2) abs(target) > total oznacza, że nie można osiągnąć target, nawet jeśli wszystkie znaki zostaną dobrane tak samo. Jeśli którykolwiek z tych warunków nie jest spełniony, należy natychmiast zwrócić 0. Dzięki tym sprawdzeniom można przejrzyście obsłużyć przypadki brzegowe bez dodawania wyjątków wewnątrz pętli DP.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Prześledzenie małego przykładu
Dla nums=[1,1,1,1,1], target=3: total=5, new_target=(3+5)//2=4. Zliczamy podzbiory o sumie 4 spośród [1,1,1,1,1]. Jest ich C(5,4)=5 (wybieramy 4 jedynki ze znakiem plus, a piątej przypisujemy znak minus: 1+1+1+1-1=3). DP poprawnie zwraca 5. To przekształcenie elegancko odwzorowuje problem przypisywania znaków na standardowy problem zliczania podzbiorów.
Obsługa zer w nums
Jeśli nums zawiera zera, przypisanie znaków + lub - do zera nie zmienia sumy. Każde zero podwaja liczbę poprawnych przypisań. DP naturalnie to obsługuje: podczas przetwarzania num=0 pętla wewnętrzna range(new_target, -1, -1) przebiega od new_target do 0, a dp[c] += dp[c - 0] = dp[c] podwaja wszystkie osiągalne sumy. Nie jest potrzebna specjalna obsługa, jeśli używają Państwo range(new_target, num-1, -1), które dla num=0 rozpoczyna się od new_target i przebiega do 0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Porównanie złożoności
DFS metodą brute force ma złożoność O(2^n). DFS z memoizacją ma złożoność O(n × total) czasowo i O(n × total) pamięciowo. Jednowymiarowe DP oparte na przekształceniu ma złożoność O(n × new_target) czasowo i O(new_target) pamięciowo, gdzie new_target ≤ total. DP 1D zużywa znacznie mniej pamięci niż memoizacja, ponieważ dzięki przekształceniu eliminuje wymiar indeksu.
Powiązanie z innymi problemami plecakowymi
Target Sum łączy kilka koncepcji związanych z problemem plecakowym: zaczyna się jako problem przypisywania, następnie zostaje przekształcony w problem sumy podzbioru (podobnie jak Partition Equal Subset Sum) i wykorzystuje ten sam szablon problemu plecakowego 0/1 z iteracją wsteczną, ale z operacją zliczania (podobnie jak Coin Change II). Opanowanie tych powiązań pozwala szybko klasyfikować nowe problemy podczas rozmów rekrutacyjnych na podstawie ich strukturalnego podobieństwa do znanych wzorców.
Przypadki brzegowe i uwagi dotyczące rozmowy
Najważniejsze przypadki: (1) target = total: istnieje tylko jeden sposób (wszystkie znaki plus); (2) target = -total: istnieje tylko jeden sposób (wszystkie znaki minus); (3) target = 0 przy samych zerach: wynik to 2^n; (4) bardzo duża wartość total przy małym n — rozmiar jednowymiarowej tablicy DP jest ograniczony przez total/2. Podczas rozmowy rekrutacyjnej warto werbalnie przeprowadzić przekształcenie przed rozpoczęciem kodowania — jest to nieoczywista obserwacja, która wyróżnia najlepszych kandydatów.
Alternatywa z DP 2D bez przekształcenia
Bez przekształcenia można zdefiniować dp[i][s] jako liczbę sposobów przypisania znaków pierwszym i liczbom tak, aby osiągnąć sumę s. Suma może być ujemna, dlatego należy przesunąć ją o total i użyć dp[i][s + total]. Wymaga to tablicy 2D o rozmiarze (n+1) × (2*total+1). To rozwiązanie jest poprawne, ale zużywa więcej pamięci i trudniej je szybko zakodować pod presją rozmowy niż jednowymiarowy problem plecakowy po zastosowaniu przekształcenia.
Szybkie sprawdzenie
Sprawdź swoje rozumienie zagadnień z zakresu Data Structures & Algorithms — Coding Interview Prep przedstawionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo następujące zagadnienia: Target Sum przekształca problem przypisywania znaków w zliczanie podzbiorów o sumie (target + total) / 2, jednowymiarowy problem plecakowy 0/1 z iteracją wsteczną zlicza podzbiory w czasie O(n × new_target) i przy użyciu O(new_target) pamięci oraz wczesne sprawdzenia poprawności (nieparzysta suma, |target| > total) zapobiegają niepotrzebnemu uruchamianiu DP. Następnie przejdziemy do problemów związanych z najkrótszymi ścieżkami, zaczynając od algorytmu Dijkstry i kolejki priorytetowej.
Często zadawane pytania
Czy lekcja „Suma docelowa ze znakami dodatnimi i ujemnymi” jest bezpłatna?
Tak — pełny tekst „Suma docelowa ze znakami dodatnimi i ujemnymi” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Suma docelowa ze znakami dodatnimi i ujemnymi”?
Przekształcać problem przypisywania znaków w problem plecakowy oparty na różnicy sum podzbiorów i rozwiązywać go w czasie O(n × sum) Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 docelowa ze znakami dodatnimi i ujemnymi”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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 i optymalizacja pamięci
- Plecak bez ograniczeń i Coin Change II
- Podział na równe sumy podzbiorów
- Suma docelowa ze znakami dodatnimi i ujemnymi