Web Analytics Made Easy - Statcounter
SVET PROGRAMIRANJA

Subset Sum — problem i detaljno objašnjenje sa DP rešenjem


1. Šta je Subset Sum?

Dat je skup celih brojeva S = {s₁, s₂, ..., sₙ} i ciljana suma T. Pitanje glasi: Postoji li podskup elemenata iz S čija suma iznosi tačno T?

Svaki element skupa može biti ili uključen u podskup ili ne, dakle rešenje se bira među svim mogućim kombinacijama elemenata.

Primer: S = {3, 1, 5, 9, 12}, T = 9 → odgovor: da (jedan mogući podskup je {3,1,5}).

2. Opis zadatka

Na osnovu skupa S i ciljne sume T, potrebno je utvrditi:

  • da li postoji podskup koji sumira tačno T,
  • po želji, pronaći jedan ili sve podskupove koji zadovoljavaju ovu sumu.

Svaki element može biti uključen najviše jednom. Podskup može biti prazan ako T = 0.

3. Moguće varijante problema

  • Decision problem: Vraća da/ne odgovor da li postoji podskup sa sumom T.
  • Counting problem: Izbrojati koliko različitih podskupova daje sumu T.
  • Construction problem: Pronaći i vratiti jedan ili sve podskupove sa sumom T.
  • Optimizacija: Naći podskup čija suma je što bliža T ako T nije moguće tačno postići.

4. Primer sa konkretnim brojevima

Ulaz:

  • Skup: S = {3, 1, 5, 9, 12}
  • Ciljna suma: T = 9

Objašnjenje:

  • Mogući podskupovi koji daju sumu 9: {3,1,5}, {9}
  • Svaki element se uzima ili ne uzima, nema deljenja ili višestrukog uzimanja istog elementa.

Izlaz:

  • Postoji podskup sa sumom T? → da
  • Primer jednog podskupa: {3,1,5}

5. Napomene i preporuke za rešavanje

  • Ovo je klasičan NP-kompletan problem u opštem slučaju, ali se često rešava dinamičkim programiranjem kada su brojevi nenegativni i T nije prevelik.
  • Efikasni pristupi uključuju:
    • Top-down rekurziju sa memoizacijom (proverava se svaki podproblem samo jednom),
    • Bottom-up tabulaciju (popunjavanje DP tabele od 0 do T),
    • Bitset optimizaciju za male/umerene T vrednosti,
    • Meet-in-the-middle pristup za veći broj elemenata (n ≤ 40).
  • Za negativne brojeve problem postaje složeniji i zahteva dodatne tehnike (pomak suma, ili hash mape).

Ovaj problem je odlična vežba za razumevanje dinamičkog programiranja i preklapajućih podproblema.

2. Brute force (zašto nije dovoljno)

Najjednostavniji pristup isproba sve podskupove — ima ih 2ⁿ. To je prihvatljivo samo za male n (n ≤ 20). Potrebno je efikasnije rešenje.

3. Dinamičko programiranje — osnovna ideja

Definišemo logički (boolean) DP niz: 

dp[sum] = true  ako je moguća suma 'sum' korišćenjem već obrađenih elemenata

Početno: dp[0] = true (prazan podskup daje sumu 0), sve ostale dp[x] su inicijalno false. Kada obradimo novi broj num, ažuriramo dp tako da uključimo sve nove sume koje dobijamo dodavanjem num na već ostvarene sume. 

for (int num : S) {
    for (int sum = T; sum >= num; --sum) {
      dp[sum] = dp[sum] || dp[sum - num];
    }
  }

Zašto iteriramo unazad (od T prema num)?

  • Ako bismo iterirali unapred (od num ka T), tada bi nova vrednost dp[x] mogla uticati na veće sume u istoj iteraciji i omogućiti da isti element bude upotrebljen više puta — što menja problem u unbounded (neograničeni) knapsack.
  • Iteracijom unazad garantujemo da se nova suma dp[sum] dobija isključivo na osnovu starih (prethodnih) stanja dp[sum - num], dakle iste vrednosti element ne koristi više puta.

4. Intuitivna objašnjenja i analogije (kockice / tegovi)

Analogia: Zamislimo da su elementi težine kockica ili tegova. Imamo neke tegove, svaki sa svojom težinom. dp[x] = true znači "u tvom ruksaku možeš formirati težinu x".

- Ako imaš samo teg težine 3, možeš dobiti težine: 0 (prazan ruksak) i 3 (uzmeš taj teg). Sve ostale težine su nemoguće. - Kada kasnije dobiješ još jedan teg, recimo 4, sada možeš napraviti i 4 (samo taj teg) i 7 (3+4). - Važno je da zapamtiš sve dosadašnje moguće težine (dp[vrednosti]) jer će uskoro novi tegovi možda dozvoliti kombinovanje sa baš tim vrednostima.

5. Detaljni korak-po-korak primeri

Primer A — samo jedan element: {3}, cilj T = 6

Početno: dp[0] = true, ostalo false.

Nakon obrade 3:

sum0123456
dptruefalsefalsetruefalsefalsefalse

Objašnjenje: možemo ili ne uzeti teg 3 → dobijamo 0 ili 3. 1 i 2 su nemoguće jer nemamo kockicu manjeg iznosa.

Primer B — dodajemo drugi element: {3, 4}, cilj T = 7

Stanje pre drugog elementa (posle 3): dp[0]=T, dp[3]=T.

Obrađujemo num = 4. Novi mogući iznosi nastaju tako što dodamo 4 na sve prethodne istinite vrednosti:

  • 0 + 4 = 4 → dp[4] = true
  • 3 + 4 = 7 → dp[7] = true
sum01234567
dptruefalsefalsetruetruefalsefalsetrue

Zaključak: dp[5] ostaje false jer da bi 5 bilo moguće trebalo bi pre toga da postoji dp[1] = true (tada 1+4=5). Pošto dp[1] = false, nemamo 5.

Primer C — dodajemo treći element: {3, 4, 2}, cilj T = 6

Posle prethodnih koraka, dp[4]=true i dp[3]=true. Sada obradimo num = 2 (iteriramo sum unazad):

  • dp[6] |= dp[4] → dp[6] = true (jer dp[4] = true i 4+2 = 6)
  • dp[5] |= dp[3] → dp[5] = true (jer dp[3] = true i 3+2 = 5)
  • dp[2] |= dp[0] → dp[2] = true

Stanje konačno (do 6): dp[6]=true → cilj dostignut.

6. Zašto pamtimo sve dp[1..T]?

Čuvamo sve međurezultate jer ne znamo koji će se elementi pojaviti kasnije. Svaki sledeći broj može kombinovati bilo koju već ostvarenu sumu. Ako ne sačuvamo dp[3] danas, ne bismo mogli kasnije formirati 3+2=5. Dakle, i one sume koje izgleda da trenutno "ne pomažu" mogu biti ključne za buduće korake.

7. Zašto se ide unazad (detaljno, još jednom)

Koristimo jednodimenzionalni dp niz radi memorijske optimizacije. Ako iteriramo sumove unapred (od num ka T), novoizračunate vrednosti u istoj iteraciji mogu biti ponovno upotrebljene, što znači da bi isti element bio iskorišćen više puta (neželjeno). Iteracijom unazad dp[sum] zavisi samo od starih vrednosti dp[sum-num], što osigurava da je svaki element uključen najviše jednom.

8. Implementacija (C++)

Efikasna implementacija koristeći O(T) memorije:


// Subset Sum (boolean) -- O(n * T) vreme, O(T) memorije
#include <iostream>
#include <vector>
using namespace std;

bool subsetSum(const vector<int>& S, int T) {
    vector<bool> dp(T+1, false);
    dp[0] = true;
    for (int num : S) {
        for (int sum = T; sum >= num; --sum) {
            dp[sum] = dp[sum] || dp[sum - num];
        }
    }
    return dp[T];
}

int main() {
    vector<int> S = {3, 4, 2};
    int T = 6;
    cout << (subsetSum(S, T) ? "Da\\n" : "Ne\\n");
    return 0;
}

Komentari uz kod

  • dp[sum] označava da li je suma moguća koristeći obrađene elemente.
  • Petlja for (int sum = T; sum >= num; --sum) osigurava da novi element ne bude iskorišćen više puta.
  • Na kraju funkcije vraćamo dp[T] — da li je ciljna suma moguća.

9. Složenost

  • Vremenska složenost: O(n · T)
  • Memorija: O(T) (može se i dodatno optimizovati u specijalnim slučajevima)

10. Saveti i česte greške

  • Ne iterirajte unapred (od num ka T) — to vodi u grešku “korišćenje elementa više puta”.
  • Zapamti da dp[0] uvek bude true (prazan podskup).
  • Ako su brojevi veliki ili ako T veoma raste, DP može postati spor ili memorijski zahtevan — tada potraži alternativne pristupe ili optimizacije (npr. bitset optimizaciju, meet-in-the-middle za n ≤ 40, ili heuristike).
  • Za brojanje načina (koliko podskupova daje sumu T) logika je slična, ali treba čuvati brojeve (long long) i paziti na prelivanje / modulo ako je potrebno.

11. Kratki rezime (za učenika)

  1. Definiši dp[sum] — da li je suma moguća.
  2. Počni sa dp[0] = true, ostalo false.
  3. Za svaki broj num ažuriraj dp unazad: za sum = T..num uradi dp[sum] |= dp[sum-num].
  4. Na kraju proveri dp[T].

Ako želiš, mogu da:

  • dodam vizuelnu DP tabelu u boji koja korak-po-korak prikazuje popunjavanje za neki primer,
  • napravim varijantu koja broji broj različitih podskupova,
  • ili dodam interaktivnu animaciju sa JavaScriptom.

Vizuelna DP tabela (korak-po-korak)

Primer: S = {3, 4, 2}, ciljna suma T = 6. Svaki red predstavlja stanje dp[] nakon obrade jednog broja.

korak 0123456
početno T F F F F F F
posle 3 T F F T F F F
posle 4 T F F T T F T
posle 2 T F T T T T T

Iz vizuelne tabele se jasno vidi kako svaka nova vrednost num omogućava nove tačne sume, i kako se dp[] postupno "popunjava" sve dok ne dostignemo cilj T = 6.

Intuitivna vizuelna ilustracija — kockice / tegovi

Problem Subset Sum možemo posmatrati kao slaganje tegova na levu stranu vage. Imamo dostupne tegove (brojeve), i želimo da vidimo koje sve težine možemo napraviti njihovim kombinovanjem.

Primer: S = {3, 4, 2}, ciljna suma T = 6.

Korak 1: Početno stanje

-- → 0 1 2 3 4 5 6

Na početku možemo napraviti samo sumu 0 jer nismo stavili nijedan teg.

Korak 2: Dodajemo teg 3

3 → 0 1 2 3 4 5 6

Jedina nova suma koju možemo formirati je 3, zato što imamo 0, i 0 + 3 = 3.

Korak 3: Dodajemo teg 4

3 4 → 0 1 2 3 4 5 6

Sada dobijamo nove moguće sume:

  • 4 (jer 0 + 4 = 4)
  • 7 (0 + 3 + 4 = 7, ali > T=6, ignorišemo za ciljnu sumu)

Korak 4: Dodajemo teg 2

3 4 2 → 0 1 2 3 4 5 6

Teg 2 donosi još nekoliko mogućih suma:

  • 2 (0 + 2)
  • 5 (3 + 2)
  • 6 (4 + 2)

Sad možemo formirati apsolutno sve sume do 6, uključujući i ciljnu sumu T=6.

Zaključak

Vizuelni model sa tegovima pomaže da se shvati ključna ideja: sve sume koje ćemo možda trebati kasnije moraju biti zapamćene u dp[] dok gradimo rešenja. Na ovaj način vidimo kako dodavanje svakog elementa „gradi“ nove moguće sume na osnovu prethodnih.

□ Rekonstrukcija podskupa – koji brojevi formiraju koju sumu?

Kada radimo Subset Sum samo sa boolean DP nizom dp[sum], znamo da li je neka suma moguća, ali ne znamo kojim brojevima. Zato pravimo posebnu strukturu koja pamti: 

parent[sum] = (prethodna_suma, broj_koji_je_dodat)

Ovo nam omogućava da “idemo unazad”, od ciljne sume T, pa pratimo koji broj ju je formirao i koja suma je postojala pre njega.

Primer

Skup: {3, 4, 5}
Ciljna suma: T = 7

Kako se popunjava parent tabela:

Suma dp[suma] parent[suma] Objašnjenje
3 true (0, 3) 3 se može formirati direktno brojem 3
4 true (0, 4) 4 se može formirati direktno brojem 4
5 true (0, 5) 5 se može formirati direktno brojem 5
7 true (3, 4) 7 = 3 + 4 → koristi se suma 3, koju smo ranije formirali

□ Rekonstrukcija podskupa za T = 7

Start: 7  
parent[7] = (3, 4)  → znači uzeli smo 4  
parent[3] = (0, 3)  → znači uzeli smo 3  
parent[0] = kraj

Rešenje:

{ 3, 4 }

C++ kod za praćenje podskupa

vector<bool> dp(T+1, false);
vector<pair<int,int>> parent(T+1, {-1,-1});

dp[0] = true;

for (int num : a) {
    for (int sum = T; sum >= num; --sum) {
        if (dp[sum - num] && !dp[sum]) {
            dp[sum] = true;
            parent[sum] = {sum - num, num};
        }
    }
}

// Rekonstrukcija
vector<int> subset;
int cur = T;

while (cur != 0 && parent[cur].first != -1) {
    subset.push_back(parent[cur].second);
    cur = parent[cur].first;
}

Vizuelna ilustracija rekonstrukcije

7   ⬑ dodali smo 4

3   ⬑ dodali smo 3

0 (početak)

To znači da je DP algoritam pronašao da se 7 formira lančano:

7 = 3 + 4

Rešenje zadatka — Subset Sum (DP sa memoizacijom)

U ovom delu nalazi se kompletno uputstvo i potpuno objašnjeno rešenje za zadatak „Subset Sum“. Ideja je da se produbi razumevanje rekurentnih odnosa, memoizacije i tabulacije, koji spadaju u osnovne tehnike dinamičkog programiranja.

NP‑kompleksnost i ograničenja DP rešenja

Subset Sum problem je poznat kao NP‑kompletan u opštem slučaju. Vikipedija objašnjava detalje. To znači da, iako DP rešenje radi u vremenu O(n·T) (gde je n broj elemenata, a T ciljna suma), ovo je pseudopolynomialno.

Pseudopolynomialno znači da vreme izvršavanja zavisi od vrednosti brojeva, a ne samo od njihove količine. Za male brojeve i umerene ciljne sume, DP je vrlo efikasan. Međutim, ako su brojevi i T veliki, složenost može postati nepraktična, i DP ne garantuje polinomsko vreme u opštem slučaju.

Alternativa za veće vrednosti i optimizacija

Kada se susretnemo sa velikim brojevima ili velikim T, postoje naprednije tehnike:

  • Meet-in-the-middle algoritam — deli skup na dve polovine i kombinuje njihove sume; ima složenost O(2^{n/2}), često praktično za n ≈ 40.
  • Heuristike i aproksimacije — za probleme gde precizno rešenje nije neophodno, omogućavaju brža rešenja.
  • Pseudopolynomialna optimizacija — neke varijante DP mogu smanjiti memoriju ili vreme, ali i dalje zavise od vrednosti brojeva.

Za dodatne detalje i formalne rezultate pogledajte arXiv: Pseudopolynomial Subset Sum algoritmi.

Zaključak: DP rešenje Subset Sum problema je vrlo korisno, ali učenici i takmičari treba da budu svesni njegovih ograničenja — nije univerzalno brzo za sve unose.

Vizuelna ilustracija pseudopolynomialnog rasta DP za Subset Sum

Sledeća tabela pokazuje primer kako DP niz dp[0..T] raste kada povećavamo ciljne sume i dodajemo brojeve. Boje označavaju da li je suma moguća (zelena) ili ne (crvena). Ovo ilustruje zašto DP postaje nepraktičan kada su brojevi veliki.

Brojevi T = 0 T = 1 T = 2 T = 3 T = 4 T = 5 T = 6
Inicijalno ✔ ✖ ✖ ✖ ✖ ✖ ✖
+ Broj 1 ✔ ✔ ✖ ✖ ✖ ✖ ✖
+ Broj 3 ✔ ✔ ✖ ✔ ✖ ✖ ✔
+ Broj 4 ✔ ✔ ✖ ✔ ✔ ✔ ✔

Legenda: ✔ suma je moguća sa trenutnim podskupom, ✖ suma nije moguća. Ova tabela vizuelno pokazuje kako dodavanje brojeva omogućava sve veći broj ciljeva, ali takođe ilustruje rast memorije sa T. Kada su T i elementi veliki (npr. T > 10⁵), DP niz postaje ogroman — iako je rešenje tačno, nije praktično.

Subset Sum — Vizuelna ilustracija podskupova (kockice/tegovi)

Sledeća ilustracija prikazuje kako različiti podskupovi brojeva mogu da formiraju određene ciljne sume T. Svaka “kockica” predstavlja broj iz skupa, a redovi pokazuju kombinacije koje doprinose sumama.

Primer skupa: nums = [1, 3, 4], cilj T = 6

Podskup Sum = 0 Sum = 1 Sum = 2 Sum = 3 Sum = 4 Sum = 5 Sum = 6
{ } ✔ ✖ ✖ ✖ ✖ ✖ ✖
{1} ✔ ✔ ✖ ✖ ✖ ✖ ✖
{3} ✔ ✖ ✖ ✔ ✖ ✖ ✖
{4} ✔ ✖ ✖ ✖ ✔ ✖ ✖
{1,3} ✔ ✔ ✖ ✔ ✖ ✔ ✖
{1,4} ✔ ✔ ✖ ✖ ✔ ✔ ✖
{3,4} ✔ ✖ ✖ ✔ ✔ ✖ ✔
{1,3,4} ✔ ✔ ✖ ✔ ✔ ✔ ✔

Legenda: ✔ suma je moguća sa datim podskupom, ✖ suma nije moguća. Svaka linija pokazuje kako kombinacije elemenata doprinose formiranju ciljne sume T.

Ova ilustracija pomaže da se intuitivno shvati zašto DP popunjava dp[sum] polje od nule do T i kako se prethodno zapamćeni rezultati kombinuju.

Subset Sum — Rekonstrukcija podskupa

Često u praktičnim zadacima nije dovoljno samo utvrditi da li je ciljna suma T moguća. Potrebno je i pronaći jedan podskup koji čini tu sumu. Ovo se može uraditi tako što pored boolean DP polja čuvamo informacije o izboru elemenata.

Ideja rešenja

  1. Kreiraj DP tabelu dp[i][sum] koja označava da li je suma sum moguća koristeći prvih i elemenata.
  2. Da bi rekonstruisali podskup, možemo pratiti odluke: za svaku dp[i][sum] čuvamo da li je suma nastala uključivanjem nums[i] ili ne.
  3. Posle popunjavanja DP tabele, počnemo od dp[n][T] i vraćamo se unazad, dodajući elemente koji su učestvovali u formiranju sume.

C++ kod — rekonstrukcija podskupa


// Subset Sum sa rekonstrukcijom jednog podskupa
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];

    vector<vector<bool>> dp(n+1, vector<bool>(T+1, false));
    vector<vector<bool>> take(n+1, vector<bool>(T+1, false));

    dp[0][0] = true;

    for(int i = 1; i <= n; i++) {
        for(int sum = 0; sum <= T; sum++) {
            // ne uzimamo nums[i-1]
            if(dp[i-1][sum]) dp[i][sum] = true;

            // uzimamo nums[i-1] ako ne prelazi sum
            if(sum - nums[i-1] >= 0 && dp[i-1][sum - nums[i-1]]) {
                dp[i][sum] = true;
                take[i][sum] = true; // oznaka da smo uzeli nums[i-1]
            }
        }
    }

    if(!dp[n][T]) {
        cout << "Nema resenja\n";
        return 0;
    }

    // rekonstruisemo podskup
    vector<int> subset;
    int sum = T;
    for(int i = n; i > 0; i--) {
        if(take[i][sum]) {
            subset.push_back(nums[i-1]);
            sum -= nums[i-1];
        }
    }

    cout << "Podskup koji daje sumu " << T << ": ";
    for(int x : subset) cout << x << " ";
    cout << "\n";

    return 0;
}

Test primeri i rubni slučajevi

  • Primer gde postoji rešenje: nums = [1, 3, 4], T = 6 → podskup: {2,4} ili {1,3,2} (jedan primer je dovoljan).
  • Primer gde nema rešenja: nums = [2,5,7], T = 4 → ispisuje Nema resenja.
  • Primer gde T veće od sume svih elemenata: nums = [1,2,3], T = 10 → nema rešenja.
  • Primer sa duplikatima: nums = [1,2,2,3], T = 4 → podskup može biti {1,3} ili {2,2}.
  • Primer sa nulom i negativnim brojevima (ako ih dozvoljavamo): nums = [0, 2, -1, 3], T = 2 → podskup može biti {2} ili {0, 3, -1}.

Ova varijanta daje kompletnu sliku — ne samo da znamo da li je suma moguća, već i koji elementi doprinose toj sumi. Ideja se lako proširuje i na pronalaženje svih mogućih podskupova.

Algoritmi
Matrice
Java
Linkovi
​Politika Privatnosti
Kontakt

© 2025 by Slobodan svetprogramiranja.com

Sva prava zadržana
SVET PROGRAMIRANJA