Subset Sums

Ako nekog ne mrzi je l moze da napise neki hint?
Unapred hvala.

nisam ga otkucao, ali sam ga sada procitao i trebalo bi da je dobra ideja.

pa ako ti je N=34, dobro poznata ideja je da podelis u 2 grupe i da radis 2* 2^(N/2)

i kada odradis prvu grupu zapamtis nekako da posle mozes da pogledas u logaritmu koliko ima suma od X1 do X2.
i dok radis drugu grupu i dodjes do nekog zbira, samo pogledas tamo gde si zapamtio koliko ima suma tako da zajedno sa ovom sumom ulaze u interval od A do B.

nadam se da sam pomogao.

Pa otprilike.
Samo jos nesto da pitam usput: ako imas jedan niz je l postoji neka funkcija da pozoves svih 2^n podniza?

mozes da napises rekurziju ...
veoma je lako ...

void Rek( int p, bool mark[n] )
{
    if ( p == n ) {
       //uradi nesto, u podnizu su svi kojima je mark[i] = true
    }
    else {
       mark[p] = true;
       Rek( p+1, mark );
       mark[p] = false;
       Rek( p+1, mark );
    }
}

ali mozes i sa for-om:

for (int i = 0; i < ( 1 << n ); i++) {
   // ( 1 << n ) = 2^n !!!
   //uradi nesto, a u podnizu su svi gde je: i & (2^j) == (2^j), gde je j, for (int j = 0; j < n; j++) !!!
   //znaci onda ide:
     for (int j = 0; j < n; j++)
        if ( i & (1<<j) == (1<<j) ) { ovaj je u podnizu }
}
// e sada mozes malo poboljsati jer ako primetis stalno racunas 2^i, gde i ide do n, pa mozes da napravis niz stepen[n+1], gde ce ga napuniti stepenima dvojke do n
// stepen[0] = 1; for (int i = 1; i <= n; i++) stepen[i] = 2*stepen[i-1];