Pretpostavimo da radimo dinamiku gdje je stanje bitmaska – koje smo elemente već iskoristili, a u prijelazu biramo neki podskup neiskorištenih elemenata.

Na prvi pogled složenost je 2^N * 2^N = 4^N, ali ne i ako prijelaz pišemo ovako:

for (int nova = ~mask; nova > 0; nova = (nova - 1) & ~mask) { ... }

To će iterirati po svim podskupovima koji su disjunktni s mask. Može se iterirati i u rastućem poretku:

for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask) { ... }

Ako ovdje ne želimo nulu, treba početi od nova = (mask + 1) & ~mask. Probajte na papiru razumjeti ove petlje i zašto funkcioniraju, inače ih vjerojatno nećete zapamtiti.

Ukupna je složenost O(3^N). Ako ne vjerujete, zavrtite ovo:

int cnt = 0;
for (int mask = 0; mask < (1 << N); mask++)
  for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask)
    ++cnt;

…i možete se uvjeriti da će cnt biti točno 3^N. Dokaz slobodno ostavite u komentarima.

Primjer zadatka: Z-most.

Tu, međutim, nije kraj optimizaciji — još efikasniji pristup, složenosti O(N * 2^N), i mnogo zadataka (uključujući jedan s HONI/COCI) možete pronaći ovdje. Hvala Patriku Paviću na ovim linkovima.