Lige sum af delmængder

Definér et boolsk array dp[c], hvor dp[c] = True betyder, at der findes en delmængde, der summerer præcis til c. Initialisér dp[0] = True (den tomme delmængde summerer til 0) og alle andre til False. For hvert tal num gennemløber du kapaciteten fra target ned til num (baglæns iteration i 0/1-rygsækproblemet) og sætter dp[c] = dp[c] or dp[c - num].

For [1, 5, 11, 5] er total=22 og target=11. I begyndelsen er dp[0]=True. Efter num=1: dp[1]=True. Efter num=5: dp[5]=True, dp[6]=True. Efter num=11: dp[11]=True (ved kun at bruge 11). Vi har allerede fundet dp[11]=True — men vi fortsætter med at behandle alle tal. Det endelige svar er: dp[11]=True, så en opdeling er mulig.

Vi kan tilføje et tidligt stop: Hvis dp[target] bliver True på noget tidspunkt, returnerer vi straks True. Det kan gøre scenarier i bedste fald markant hurtigere. Hvis et enkelt element er lig med target, kan vi også straks returnere True. Hvis et enkelt element overstiger target, kan det ikke indgå i en delmængde, der summerer til target, men vi skal stadig kontrollere resten.

Et alternativ er at vedligeholde en mængde med opnåelige summer. Begynd med {0}. For hvert tal føjer du tallet til hver sum i den aktuelle mængde: reachable = reachable | {s + num for s in reachable}. Filtrér, så du kun beholder summer, der ikke overstiger target. Til sidst tjekker du, om target findes i mængden. Denne tilgang er intuitiv, men kan bruge mere hukommelse og kan være langsommere i praksis.

DP-tilgangen kører i tiden O(n × S), hvor S = sum(nums), og bruger O(S) hukommelse til det boolske array. For begrænsningerne i LeetCode (n ≤ 200, sum ≤ 20.000) er det højst 4.000.000 operationer — meget hurtigt. Mængdetilgangen har samme asymptotiske kompleksitet, men kan være langsommere i praksis på grund af omkostningerne ved at opbygge mængder.

Et beslægtet problem er at tælle antallet af delmængder, der summerer til et mål. Ændr DP'en fra boolsk til heltalsbaseret: dp[c] = number of ways to reach sum c. Brug addition i stedet for OR: dp[c] += dp[c - num]. Initialisér dp[0] = 1. Brug den samme baglæns iteration. Denne generalisering viser, hvordan skabelonen for rygsækproblemet tilpasses forskellige spørgsmål om delmængder.

Forvent opfølgende spørgsmål: (1) Hvad hvis du skal returnere den faktiske opdeling? — det kræver 2D-DP til rekonstruktion. (2) Hvad hvis elementerne kan være negative? — forskyd target, eller brug en ordbog i stedet for et array. (3) Hvad er tidskompleksiteten? — O(n × sum). (4) Kan du forbedre løsningen, hvis mange tal er ens? — ja, brug frekvensoptælling til at reducere antallet af ydre iterationer. Nævn altid disse afvejninger proaktivt.

Problemet med opdeling i delmængder med samme sum er en direkte anvendelse af 0/1-rygsækproblemet: Elementerne er tallene, vægtene er lig med værdierne, og rygsækkens kapacitet er lig med target. Vi spørger, om den maksimale værdi er lig med target (gennemførlighed), ikke hvad den maksimale værdi er. Den baglæns iteration er den samme; kun operationen ændres fra max til boolsk or. Hvis du genkender denne forbindelse til en jobsamtale, viser det stærk mønstergenkendelse.

Særtilfælde, der skal håndteres: (1) array med længde 1 — et enkelt element kan ikke opdeles, så resultatet er altid False; (2) alle elementer er identiske, og antallet er lige — det fungerer måske eller måske ikke afhængigt af de enkelte værdier; (3) meget store summer — tjek begrænsningerne, før du allokerer DP-arrayet; (4) elementer, der er større end target — de kan springes over, fordi de aldrig kan indgå i en delmængde, der summerer til target. Tjekket af det største element som tidligt stop håndterer tilfælde (4) effektivt.

I denne lektion lærte du: Problemet med partitionering i delmængder med samme sum reduceres til delmængdesum med target = total//2, det boolske 1D-DP-array dp[c] bruger baglæns iteration, som er identisk med 0/1-rygsækproblemet, og tilgangen generaliseres til optælling af delmængder ved at erstatte boolsk OR med heltalsaddition. Nu tager vi fat på målsum, hvor fortegnstildelinger omdannes til et rygsækproblem baseret på forskellen mellem delmængdesummer.