Partition Equal Subset Sum

Gegeven een niet-lege array met positieve gehele getallen nums, bepaal je of je deze kunt verdelen in twee deelverzamelingen met gelijke som. Zo kan [1, 5, 11, 5] bijvoorbeeld worden verdeeld in [1, 5, 5] en [11], die allebei optellen tot 11. Als de totale som oneven is, is het antwoord meteen False. Anders moeten we een deelverzameling vinden waarvan de som gelijk is aan total_sum // 2 — een klassiek deelverzamelingensomprobleem.

De belangrijkste herleiding: als de totale som S even is en een deelverzameling optelt tot S//2, tellen de overgebleven elementen automatisch ook op tot S//2. Dus het probleem van gelijke sommen van deelverzamelingen reduceert tot de vraag: telt een deelverzameling van nums op tot S//2? Dit is het klassieke NP-volledige probleem van de som van een deelverzameling, dat we oplossen met dynamische programmering voor het 0/1-rugzakprobleem in O(n × S)-tijd.

Definieer een booleaanse array dp[c], waarbij dp[c] = True betekent dat er een deelverzameling bestaat met een som van precies c. Initialiseer dp[0] = True (de lege deelverzameling heeft som 0) en alle andere waarden met False. Doorloop voor elk getal num de capaciteit van target omlaag tot num (achterwaartse iteratie bij het 0/1-rugzakprobleem) en stel dp[c] = dp[c] or dp[c - num] in.

Voor [1, 5, 11, 5] geldt total=22 en target=11. Aanvankelijk is dp[0]=True. Na num=1: dp[1]=True. Na num=5: dp[5]=True, dp[6]=True. Na num=11: dp[11]=True (waarbij alleen 11 wordt gebruikt). We hebben dp[11]=True al gevonden, maar we blijven alle getallen verwerken. Het uiteindelijke antwoord is: dp[11]=True, dus een partitie is mogelijk.

We kunnen een vroegtijdige stop toevoegen: als dp[target] op enig moment True wordt, geef dan onmiddellijk True terug. Dit kan scenario's waarin het doel snel wordt bereikt aanzienlijk versnellen. Als één afzonderlijk element gelijk is aan target, kunnen we ook meteen True teruggeven. Als één afzonderlijk element groter is dan target, kan het geen deel uitmaken van een deelverzameling met som target, maar we moeten de rest nog steeds controleren.

Een alternatief is om een verzameling bereikbare sommen bij te houden. Begin met {0}. Voeg voor elk getal het getal toe aan elke som in de huidige verzameling: reachable = reachable | {s + num for s in reachable}. Filter de waarden zodat alleen sommen overblijven die target niet overschrijden. Controleer aan het einde of target in de verzameling zit. Deze aanpak is intuïtief, maar kan meer geheugen gebruiken en in de praktijk trager zijn.

De DP-aanpak werkt in O(n × S)-tijd, waarbij S = sum(nums), en gebruikt O(S)-ruimte voor de booleaanse array. Voor de beperkingen van LeetCode (n ≤ 200, sum ≤ 20.000) zijn dat hoogstens 4.000.000 bewerkingen — zeer snel. De verzamelingsaanpak heeft dezelfde asymptotische complexiteit, maar kan in de praktijk trager zijn door het extra werk voor het opbouwen van verzamelingen.

Een verwant probleem is het tellen van het aantal deelverzamelingen met een bepaalde doelwaarde. Verander de DP van booleaans naar een geheel getal: dp[c] = number of ways to reach sum c. Gebruik optellen in plaats van OR: dp[c] += dp[c - num]. Initialiseer dp[0] = 1. Gebruik dezelfde achterwaartse iteratie. Deze generalisatie laat zien hoe het rugzaksjabloon zich aanpast aan verschillende vragen over deelverzamelingen.

Verwacht vervolgvragen zoals: (1) Wat als je de daadwerkelijke partitie moet teruggeven? — daarvoor is 2D-DP voor reconstructie nodig. (2) Wat als elementen negatief mogen zijn? — verschuif target of gebruik een woordenboek in plaats van een array. (3) Wat is de tijdcomplexiteit? — O(n × sum). (4) Kun je de aanpak verbeteren als veel getallen hetzelfde zijn? — ja, gebruik frequentietellingen om het aantal buitenste iteraties te verminderen. Benoem deze afwegingen altijd uit jezelf.

Het probleem van gelijke sommen van deelverzamelingen is een directe toepassing van het 0/1-rugzakprobleem: de getallen zijn de objecten, de gewichten zijn gelijk aan de waarden en de capaciteit van de rugzak is gelijk aan target. We vragen of de maximale waarde gelijk is aan target (haalbaarheid), niet wat de maximale waarde is. De achterwaartse iteratie is hetzelfde; alleen de bewerking verandert van max in de booleaanse bewerking or. Als je dit verband tijdens een sollicitatiegesprek herkent, laat dat zien dat je patronen goed kunt herkennen.

Verwerk de volgende randgevallen: (1) array met lengte 1 — één element kan niet worden opgesplitst, dus het resultaat is altijd False; (2) alle elementen zijn gelijk en het aantal elementen is even — dit kan afhankelijk van de afzonderlijke waarden wel of niet werken; (3) zeer grote sommen — controleer de beperkingen voordat je de DP-array toewijst; (4) elementen die groter zijn dan target — deze kun je overslaan, omdat ze nooit deel kunnen uitmaken van een deelverzameling met som target. De controle van het grootste element als vroegtijdige stop verwerkt geval (4) efficiënt.

In deze les heb je geleerd: het probleem van gelijke sommen van deelverzamelingen reduceert tot het probleem van een deelverzamelingssom met target = total//2, de booleaanse 1D-DP dp[c] gebruikt achterwaartse iteratie, net als het 0/1-rugzakprobleem, en je kunt de aanpak uitbreiden naar het tellen van deelverzamelingen door booleaanse OR te vervangen door optellen van gehele getallen. Hierna behandelen we het probleem van de doelsom, waarbij teken toewijzen wordt omgezet in een rugzakprobleem op basis van verschillen tussen deelverzamelingssommen.