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

Š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}).

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.

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.

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}

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.

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.

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.

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.

Detaljni korak-po-korak primeri

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

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

Nakon obrade 3:

sum	0	1	2	3	4	5	6
dp	true	false	false	true	false	false	false

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

sum	0	1	2	3	4	5	6	7
dp	true	false	false	true	true	false	false	true

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.

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.

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.

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.

Složenost

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

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.

Kratki rezime (za učenika)

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

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	0	1	2	3	4	5	6
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

Tekst zadatka — Subset Sum

Dat je niz od n pozitivnih celih brojeva nums[] i ciljna suma T.

Potrebno je odrediti da li postoji podskup elemenata niza (svaki element se može koristiti najviše jednom) čija je suma elemenata tačno jednaka T.

Ako takav podskup postoji, ispisati YES, u suprotnom ispisati NO.

Ulaz

Prva linija sadrži dva cela broja n i T
Druga linija sadrži n celih pozitivnih brojeva — elemente niza

Izlaz

Ispisati YES ako postoji podskup sa sumom T
U suprotnom ispisati NO

Napomena

Svaki element niza može se koristiti najviše jednom
Zadatak zahteva samo proveru postojanja, ne i ispis samog podskupa

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.

Uputstvo — ideja rešenja

Imamo niz pozitivnih brojeva nums[] i ciljnu sumu T. Treba da utvrdimo da li postoji podskup elemenata koji sabiranjem daje tačno T.

dp[i][sum] = da li je moguće dobiti sumu 'sum' koristeći prva i elemenata

Rekurentna relacija:

dp[i][sum] = dp[i-1][sum] || dp[i-1][sum - nums[i-1]]

Intuicija: za element nums[i-1] možemo:

Ne uzeti ga → dp[i-1][sum]
Uzeti ga → dp[i-1][sum - nums[i-1]]

Osnovni slučajevi

dp[0][0] = true (prazan skup daje sumu 0)
dp[0][sum ≠ 0] = false (ne možemo dobiti pozitivnu sumu sa 0 elemenata)

Zašto DP?

Bez pamćenja, obična rekurzija proverava iste kombinacije više puta. DP čuva rezultate za kombinacije sum+indeks, izbegavajući eksponencijalnu složenost.

Top-down (memoizacija)

Implementiramo funkciju koja proverava za i i sum, a rezultate pamti.

Bottom-up (tabulacija)

Kreiramo dp niz dp[0..T] ili dp[0..n][0..T] i popunjavamo redom.

Rešenje — C++ (top-down memoizacija)


// Subset Sum — top-down memoizacija
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> memo;

bool subsetSum(const vector<int>& nums, int i, int sum) {
    if (sum == 0) return true;
    if (i == 0) return false;
    if (memo[i][sum] != -1) return memo[i][sum];

    if (sum < nums[i-1]) 
        memo[i][sum] = subsetSum(nums, i-1, sum);
    else
        memo[i][sum] = subsetSum(nums, i-1, sum) || subsetSum(nums, i-1, sum - nums[i-1]);

    return memo[i][sum];
}

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

    memo.assign(n+1, vector<int>(T+1, -1));

    cout << (subsetSum(nums, n, T) ? "YES" : "NO") << "\n";
    return 0;
}

Bottom-up tabulacija (iterativno)


// Subset Sum — bottom-up
#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<bool> dp(T+1,false);
    dp[0] = true; // prazni podskup

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

    cout << (dp[T] ? "YES" : "NO") << "\n";
}

Objašnjenje koda

Top-down pamti rezultate za svaki indeks i sumu da se izbegne duplo računanje.
Bottom-up kreće od praznog skupa i postepeno kombinuje brojeve u sumu.
Prolazimo unazad (sum=T..num) da ne prepišemo podatke koji će biti korišćeni u istoj iteraciji.

Primer

Ulaz:
5 9
3 34 4 12 5

Izlaz:
YES

Objašnjenje:
Postoji podskup {4, 3, 2} koji sabiranjem daje 9.

Vremenska i memorijska složenost

Vreme: O(n*T)
Memorija: O(n*T) za dvodimenzionalni DP ili O(T) za optimizovani bottom-up

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 DP tabele čuvamo i informaciju o tome da li je neki element zaista morao biti izabran.

Ideja rešenja

Kreiramo DP tabelu dp[i][sum] koja označava da li je suma sum moguća koristeći prvih i elemenata.
Pomoćna tabela take[i][sum] se postavlja na true samo ako je uzimanje elementa jedini način da se dobije ta suma.
Posle popunjavanja DP tabele, počinjemo od dp[n][T] i vraćamo se unazad, koristeći take da rekonstrušemo jedan validan podskup.

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++) {

            // slučaj: ne uzimamo nums[i-1]
            if(dp[i-1][sum]) {
                dp[i][sum] = true;
            }

            // slučaj: uzimamo nums[i-1] (ali samo ako je to jedini način)
            if(sum >= nums[i-1] && dp[i-1][sum - nums[i-1]] && !dp[i-1][sum]) {
                dp[i][sum] = true;
                take[i][sum] = true;
            }
        }
    }

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

    // rekonstrukcija podskupa
    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 granični slučajevi

Primer gde postoji rešenje: nums = [1, 3, 4], T = 5 → podskup: {1,4}.
Primer gde nema rešenja: nums = [2,5,7], T = 4 → ispisuje Nema resenja.
Primer gde je 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 {2,2} ili {1,3}.

Ova implementacija garantuje da je rekonstruisani podskup uvek u skladu sa DP tabelom. Matrica take se koristi isključivo za odluke koje su bile neophodne, čime se izbegavaju nekonzistentne rekonstrukcije.

Kako funkcioniše rekonstrukcija podskupa (vizuelno objašnjenje)

Nakon što je DP tabela dp popunjena, znamo da li je ciljna suma T dostižna, ali još uvek ne znamo koji elementi su korišćeni. Zato koristimo pomoćnu tabelu take.

Ključna ideja je sledeća:

take[i][sum] = true znači da se suma sum ne može dobiti bez uzimanja elementa nums[i-1].

Ako je suma mogla da se dobije i bez tog elementa, take[i][sum] ostaje false, čak i ako je uzimanje takođe bilo moguće.

Primer

Neka su dati brojevi:


nums = [1, 3, 4]
T = 5

DP tabela (1 = moguće)


        suma →
i ↓     0 1 2 3 4 5
-------------------
0       1 0 0 0 0 0
1 (1)   1 1 0 0 0 0
2 (3)   1 1 0 1 1 0
3 (4)   1 1 0 1 1 1

Označene `take` odluke

Pogledajmo kako se dobija dp[3][5]:

Bez broja 4: dp[2][5] = false
Sa brojem 4: dp[2][1] = true

Pošto ne postoji rešenje bez broja 4, postavljamo:


take[3][5] = true

Vizuelno kretanje unazad (rekonstrukcija)


Start: (i=3, sum=5)
  |
  |-- take[3][5] = true → uzimamo 4
  |
(i=2, sum=1)
  |
  |-- take[2][1] = false → ne uzimamo 3
  |
(i=1, sum=1)
  |
  |-- take[1][1] = true → uzimamo 1
  |
(i=0, sum=0)  ✓

Rekonstruisani podskup je:


{1, 4}

Zašto ovo uvek radi?

take se postavlja samo kada je odluka bila neizbežna.
Tokom rekonstrukcije nikada ne ulazimo u stanje koje DP tabela ne podržava.
Uvek dobijamo validan podskup, bez kontradikcija.

Ovaj pristup daje jasan i pouzdan način da se, pored informacije da li rešenje postoji, dobije i konkretan primer tog rešenja.

Varijante zadatka problema podskupa sa zadatom sumom(SubsetSum engl.)

1. Subset Sum — osnovni problem (YES / NO)

Tekst zadatka

Dat je niz nums[ ] od n pozitivnih celih brojeva i ciljna suma T. Potrebno je utvrditi da li postoji podskup elemenata niza čija suma iznosi tačno T. Svaki element se može koristiti najviše jednom. Ako postoji — ispisati YES, inače NO.

Primer

Ulaz:
5 9
3 34 4 12 5

Izlaz:
YES

Objašnjenje:
Postoji podskup {4, 5} koji sabiranjem daje 9.

Rešenje — bottom-up (optimizovano)


// Subset Sum -- bottom-up (O(T) memorije)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, T;
    if(!(cin >> n >> T)) return 0;
    vector nums(n);
    for(int i=0;i> nums[i];

    vector dp(T+1, false);
    dp[0] = true;

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

    cout << (dp[T] ? "YES" : "NO") << endl;
    return 0;
}

Napomena

Za veoma velika T vrednosti (npr. suma elemenata veoma velika) razmotri alternativne pristupe (meet-in-the-middle, ograničenja ulaza).

2. Subset Sum — rekonstrukcija rešenja

Tekst zadatka

Pored odgovora YES/NO, vratiti i konkretan podskup indeksa elemenata koji daju sumu T. Ako postoji više rešenja, vratiti bilo koje jedno. Ako ne postoji — ispisati NO.

Primer

Ulaz:
5 9
3 34 4 12 5

Izlaz:
YES
Izabrani indeksi (1-based): 3 5

Objašnjenje:
nums[3]=4, nums[5]=5 → 4+5=9

Rešenje — rekonstrukcija iz 2D DP tabele


// Subset Sum -- rekonstrukcija rešenja iz 2D DP tabele
// Skraćena i korektna varijanta BEZ dodatne take matrice
#include <iostream>
#include <vector>
#include <algorithm>
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];

    // dp[i][s] = true ako se suma s može dobiti koristeći prvih i elemenata
    vector<vector<bool>> dp(n + 1, vector<bool>(T + 1, false));

    // Osnovni slučaj:
    // Sa 0 elemenata možemo dobiti samo sumu 0
    dp[0][0] = true;

    // Popunjavanje DP tabele
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= T; s++) {

            // 1) Ne uzimamo i-ti element
            // Ako je suma s bila moguća bez njega, ostaje moguća
            if (dp[i - 1][s]) {
                dp[i][s] = true;
            }

            // 2) Uzimamo i-ti element (ako ne prelazi trenutnu sumu)
            // Proveravamo da li je s - nums[i-1] bilo moguće ranije
            if (s >= nums[i - 1] && dp[i - 1][s - nums[i - 1]]) {
                dp[i][s] = true;
            }
        }
    }

    // Ako ciljna suma nije dostižna
    if (!dp[n][T]) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";

    // ============================
    // Rekonstrukcija rešenja
    // ============================
    // Krećemo od dp[n][T] i idemo unazad
    int s = T;
    vector<int> chosen;

    for (int i = n; i > 0; i--) {

        // Ako bez i-tog elementa NIJE bilo moguće dobiti sumu s,
        // onda smo MORALI da uzmemo i-ti element
        if (s >= nums[i - 1] && !dp[i - 1][s]) {
            chosen.push_back(i);   // čuvamo indeks (1-based)
            s -= nums[i - 1];      // smanjujemo preostalu sumu
        }

        // U suprotnom, element i nije uzet
        // i samo prelazimo na i-1
    }

    // Indekse smo sakupljali unazad, pa ih obrćemo
    reverse(chosen.begin(), chosen.end());

    cout << "Izabrani indeksi: ";
    for (int idx : chosen)
        cout << idx << " ";
    cout << "\n";

    return 0;
}

Napomena

Ova verzija koristi samo DP tabelu dp i rekonstrukciju direktno iz nje. Ključna ideja je da je element uzet ako bez njega suma ne bi bila moguća. Ovo daje jednostavnije i robusnije rešenje bez dodatnih pomoćnih matrica.

3. Subset Sum — koliko različitih podskupova daje sumu T?

Tekst zadatka

Izračunati broj različitih podskupova niza nums čija suma iznosi tačno T. Ispisati broj (ako postoji mogućnost preliva, koristiti 64-bitni tip ili modulo).

Primer

Ulaz:
4 5
1 2 3 2

Izlaz:
3

Objašnjenje:
Podskupovi koji daju 5: {1,2,2} (s različitim indeksima),
{2,3} (različiti izbor indeksa za 2) — ukupno 3 načina.

Uputstvo

Ovo je counting varijanta Subset Sum problema (ne samo proveravanje postojanja).
Definicija DP-a:
dp[s] = broj različitih podskupova čija je suma tačno s.
Osnovni slučaj:
dp[0] = 1 (prazan skup — jedan validan način).
Prelaz (1D optimizacija):
za svaki broj num i sumu s (unazad): dp[s] += dp[s - num].
Iteracija suma unazad je obavezna kako bi se svaki element koristio najviše jednom.

Matematičko objašnjenje DP relacije

Neka je dp[s] broj podskupova koji daju sumu s koristeći prvih k elemenata niza. Razmotrimo sledeći element num.

Svaki podskup koji daje sumu s spada u jednu od dve disjunktne grupe:

Podskupovi koji ne koriste element num
— njihov broj je već sadržan u trenutnoj vrednosti dp[s].
Podskupovi koji koriste element num
— ako iz takvog podskupa uklonimo num, preostali elementi moraju davati sumu s - num, a takvih podskupova ima tačno dp[s - num].

Pošto su ove dve grupe međusobno disjunktne, ukupan broj podskupova sa sumom s jednak je zbiru:

dp[s] = dp[s] + dp[s - num]

Iteracija suma unazad obezbeđuje da se svaki element koristi najviše jednom, jer se vrednosti dp[s - num] odnose na stanje pre dodavanja trenutnog elementa.

Na ovaj način DP tačno prebrojava sve različite podskupove, pri čemu se elementi sa različitim indeksima smatraju različitim, čak i ako imaju istu vrednost.

Rešenje — broj načina (1D DP)


// Subset Sum — broj različitih podskupova sa sumom T
// Vremenska složenost: O(n * T)
// Memorijska složenost: O(T)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    cin >> n >> T;

    // Učitavanje niza
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // dp[s] = broj podskupova čija je suma tačno s
    vector<long long> dp(T + 1, 0);

    // Jedan način da se dobije suma 0 — prazan skup
    dp[0] = 1;

    // Za svaki element niza
    for (int num : nums) {
        // Iteriramo sume UNAZAD da se element ne bi koristio više puta
        for (int s = T; s >= num; --s) {
            dp[s] += dp[s - num];
            // Ako je potreban modulo:
            // dp[s] %= 1000000007LL;
        }
    }

    // Odgovor je broj podskupova sa sumom T
    cout << dp[T] << "\n";
    return 0;
}

Napomena

Ako se ne koristi modulo, a broj kombinacija može biti veoma velik, koristi long long ili unsigned long long, u skladu sa ograničenjima zadatka.

4. Subset Sum — minimalan broj elemenata

Tekst zadatka

Naći najmanji broj elemenata niza nums tako da njihova suma bude tačno T. Ako nije moguće, ispisati -1 (ili neku poruku da nema rešenja).

Primer

Ulaz:
5 9
3 34 4 12 5

Izlaz:
2

Objašnjenje:
4 + 5 = 9 → minimalni broj elemenata = 2

Rešenje — minimalan broj elemenata (1D DP)


// Subset Sum: minimalan broj elemenata da bi suma bila T
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    if(!(cin >> n >> T)) return 0;

    // Učitavanje elemenata niza
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    // Velika vrednost koja predstavlja "nemoguće"
    const int INF = 1000000000;

    // dp[s] = minimalan broj elemenata potreban da se dobije suma s
    vector<int> dp(T + 1, INF);

    // Osnovni slučaj: suma 0 se dobija sa 0 elemenata
    dp[0] = 0;

    // Glavna DP petlja
    for(int num : nums){
        // Iteriramo unazad da bismo sprečili višestruko korišćenje istog elementa
        for(int s = T; s >= num; --s){
            // Ako je suma (s - num) bila moguća,
            // proveravamo da li dodavanje ovog elementa daje bolje (manje) rešenje
            if(dp[s - num] != INF){
                dp[s] = min(dp[s], dp[s - num] + 1);
            }
        }
    }

    // Ako dp[T] nije promenjen, nema rešenja
    if(dp[T] == INF){
        cout << -1 << "\n";
    } else {
        cout << dp[T] << "\n";
    }

    return 0;
}

Napomena

Ovaj zadatak je varijanta 0/1 Subset Sum problema, ali umesto provere postojanja tražimo minimum. Struktura DP-a ostaje ista, menja se samo značenje dp[s] i prelazna relacija.

5. Veza sa 0/1 Knapsack problemom

Tekst zadatka / ideja

0/1 Knapsack: imamo n predmeta sa težinama w[i] i vrednostima v[i], i kapacitet ranca W. Cilj je da se maksimizuje zbir vrednosti bez prelaska ukupne težine W.

Povezanost: Subset Sum je poseban slučaj Knapsack problema. Ako postavimo v[i] = w[i] i pitamo da li možemo dobiti tačno vrednost T, dobijamo Subset Sum. Obrnuto, Knapsack je generalizacija jer dozvoljava različite težine i vrednosti.

Rešenje — 0/1 Knapsack (bottom-up, sa rekonstrukcijom)


// 0/1 Knapsack -- DP i rekonstrukcija (2D dp tabela)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;

    // wt[i]  - težina i-tog predmeta
    // val[i] - vrednost i-tog predmeta
    vector<int> wt(n), val(n);
    for (int i = 0; i < n; i++) cin >> wt[i];
    for (int i = 0; i < n; i++) cin >> val[i];

    // dp[i][w] = maksimalna vrednost koju možemo dobiti
    // koristeći prvih i predmeta i kapacitet w
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Popunjavanje DP tabele
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {

            // 1) Ne uzimamo i-ti predmet
            dp[i][w] = dp[i - 1][w];

            // 2) Uzimamo i-ti predmet (ako ima mesta u rancu)
            if (w >= wt[i - 1]) {
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]
                );
            }
        }
    }

    // Maksimalna ostvariva vrednost
    cout << "Maksimalna vrednost: " << dp[n][W] << "\n";

    // ============================
    // Rekonstrukcija izabranih predmeta
    // ============================
    int w = W;
    vector<int> chosen;

    // Idemo unazad kroz DP tabelu
    for (int i = n; i > 0; i--) {

        // Ako se vrednost promenila u odnosu na prethodni red,
        // znači da je i-ti predmet uzet
        if (dp[i][w] != dp[i - 1][w]) {
            chosen.push_back(i);     // čuvamo indeks (1-based)
            w -= wt[i - 1];          // smanjujemo preostali kapacitet
        }
        // U suprotnom, predmet nije uzet
    }

    // Obrćemo redosled jer smo išli unazad
    reverse(chosen.begin(), chosen.end());

    cout << "Izabrani predmeti: ";
    for (int x : chosen) cout << x << " ";
    cout << "\n";

    return 0;
}

Praktična upotreba

Subset Sum se može posmatrati kao Knapsack gde su težine i vrednosti jednake.
Tehnika rekonstrukcije je ista u oba problema — razlika je samo u kriterijumu optimizacije.
Razumevanje ove veze pomaže da se lakše prepoznaju DP problemi u praksi.

6. Napredne varijante Subset Sum-a

Pregled zadataka

Subset Sum sa negativnim brojevima
Neograničeno korišćenje elemenata (unbounded)
Meet-in-the-middle (n ≤ 40)
Najbliža suma ≤ T (approx / closest)

Rešenje — primeri kodova

a) Subset Sum sa negativnim brojevima — unordered_set


// Subset Sum sa negativnim brojevima koristeći skup suma
// Ideja: čuvamo sve moguće sume do sada, bez ograničenja na [0..T]
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main(){
    int n, T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // Skup svih trenutno dostižnih suma
    unordered_set<int> sums;
    sums.insert(0);  // prazni skup daje sumu 0

    for(int x : a){
        vector<int> add;
        // Za svaku postojeću sumu, dodajemo novu sumu s + x
        for(int s : sums)
            add.push_back(s + x);

        // Dodajemo nove sume u skup
        for(int v : add)
            sums.insert(v);
    }

    cout << (sums.count(T) ? "YES\n" : "NO\n");
    return 0;
}

Napomena: Ovaj pristup je praktičan kada broj različitih suma ostaje razuman. Ako se skup previše uveća, preporučuje se meet-in-the-middle.

b) Meet-in-the-middle (n ≤ 40)


// Meet-in-the-middle: proveravamo da li postoji podskup sa sumom T
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Generiše sve moguće sume podskupova niza a
void genSums(const vector<int>& a, vector<long long>& out){
    int m = a.size();
    int total = 1 << m; // 2^m kombinacija

    out.reserve(total);
    for(int mask = 0; mask < total; mask++){
        long long s = 0;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
                s += a[i];
        out.push_back(s);
    }
}

int main(){
    int n;
    long long T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int mid = n / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());

    vector<long long> L, R;
    genSums(left, L);
    genSums(right, R);

    sort(R.begin(), R.end());

    bool ok = false;
    for(long long x : L){
        long long need = T - x;
        if(binary_search(R.begin(), R.end(), need)){
            ok = true;
            break;
        }
    }

    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

c) Neograničeno korišćenje elemenata (unbounded)


// Unbounded Subset Sum (Coin Change tip)
// Svaki element se može koristiti više puta
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    // dp[s] = da li možemo dobiti sumu s
    vector<char> dp(T + 1, 0);
    dp[0] = 1;

    // Ključna razlika: iteracija po sumi ide NAPRED
    for(int i = 0; i < n; i++){
        for(int s = a[i]; s <= T; s++){
            if(dp[s - a[i]])
                dp[s] = 1;
        }
    }

    cout << (dp[T] ? "YES\n" : "NO\n");
    return 0;
}

d) Najbliža suma ≤ T (meet-in-the-middle)


// Meet-in-the-middle za pronalaženje najveće sume <= T
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

void genSums(const vector<int>& a, vector<long long>& out){
    int m = a.size();
    int total = 1 << m;

    out.reserve(total);
    for(int mask = 0; mask < total; mask++){
        long long s = 0;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
                s += a[i];
        out.push_back(s);
    }
}

int main(){
    int n;
    long long T;
    cin >> n >> T;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int mid = n / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());

    vector<long long> L, R;
    genSums(left, L);
    genSums(right, R);

    sort(R.begin(), R.end());

    long long best = LLONG_MIN;

    for(long long x : L){
        long long rem = T - x;
        auto it = upper_bound(R.begin(), R.end(), rem);
        if(it != R.begin()){
            --it;
            best = max(best, x + *it);
        }
    }

    if(best == LLONG_MIN) cout << "NO\n";
    else cout << best << "\n";

    return 0;
}

Zaključak

Ove varijante pokazuju kako se osnovni Subset Sum može proširiti: promenom DP stanja, dozvoljavanjem ponavljanja, ili kombinovanjem sa drugim tehnikama poput meet-in-the-middle.

Prethodno
|< DP: Najduži zajednički podniz (LCS)

Sledeće
Zamena iteracija formulom >|

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

Šta je Subset Sum?

Opis zadatka

Moguće varijante problema

Primer sa konkretnim brojevima

Napomene i preporuke za rešavanje

Brute force (zašto nije dovoljno)

Dinamičko programiranje — osnovna ideja

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

Intuitivna objašnjenja i analogije (kockice / tegovi)

Detaljni korak-po-korak primeri

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

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

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

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

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

Implementacija (C++)

Komentari uz kod

Složenost

Saveti i česte greške

Kratki rezime (za učenika)

Vizuelna DP tabela (korak-po-korak)

Intuitivna vizuelna ilustracija — kockice / tegovi

Korak 1: Početno stanje

Korak 2: Dodajemo teg 3

Korak 3: Dodajemo teg 4

Korak 4: Dodajemo teg 2

Zaključak

Rekonstrukcija podskupa – koji brojevi formiraju koju sumu?

Primer

Kako se popunjava parent tabela:

□ Rekonstrukcija podskupa za T = 7

C++ kod za praćenje podskupa

Vizuelna ilustracija rekonstrukcije

Tekst zadatka — Subset Sum

Ulaz

Izlaz

Napomena

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

Uputstvo — ideja rešenja

Osnovni slučajevi

Zašto DP?

Top-down (memoizacija)

Bottom-up (tabulacija)

Rešenje — C++ (top-down memoizacija)

Bottom-up tabulacija (iterativno)

Objašnjenje koda

Primer

Vremenska i memorijska složenost

NP‑kompleksnost i ograničenja DP rešenja

Alternativa za veće vrednosti i optimizacija

Vizuelna ilustracija pseudopolynomialnog rasta DP za Subset Sum

Subset Sum — Vizuelna ilustracija podskupova (kockice/tegovi)

Subset Sum — Rekonstrukcija podskupa

Ideja rešenja

C++ kod — rekonstrukcija podskupa

Test primeri i granični slučajevi

Kako funkcioniše rekonstrukcija podskupa (vizuelno objašnjenje)

Primer

DP tabela (1 = moguće)

Označene take odluke

Vizuelno kretanje unazad (rekonstrukcija)

Zašto ovo uvek radi?

Varijante zadatka problema podskupa sa zadatom sumom(SubsetSum engl.)

1. Subset Sum — osnovni problem (YES / NO)

Tekst zadatka

Primer

Uputstvo

Rešenje — bottom-up (optimizovano)

Napomena

2. Subset Sum — rekonstrukcija rešenja

Tekst zadatka

Primer

Uputstvo

Rešenje — rekonstrukcija iz 2D DP tabele

Napomena

3. Subset Sum — koliko različitih podskupova daje sumu T?

Tekst zadatka

Primer

Uputstvo

Označene `take` odluke