[ urosk @ 16.02.2005. 08:28 ] @
Treba mi algoritam koji daje sve kombinacije iz odredjenog skupa brojeva ciji je zbir jednak nekom unapred zadatom broju,
recimo zbir koji trazim je 20 a moguci brojevi su iz skupa 1, 3, 4, 5, 10, 11, 15.... trebaju mi sve kombinacije bilo kog reda npr (15,1,4) (10,4,5,1) (11,4,5) (15,5)...
[ urosk @ 16.02.2005. 10:39 ] @
Nista, uradjeno je.
[ Alef @ 16.02.2005. 11:43 ] @
Pošto tražiš samo algoritam, evo jedna mogućnost u Python-u.

Code:

from copy import copy

lista = []        # pomocna lista
kombinacije = []    # lista sa kombinacijama

def insert(lista):
    """ Proverava da li se ovaj *skup* brojeva koji prosledjujemo
    funkciji u obliku liste *lista* vec nalazi u listi *kombinacije* """ 

    for i in kombinacije:
        if set(i) == set(lista):  # set pretvara liste u skupovni tip
            return
    kombinacije.append(copy(lista))



def komb(sum, tren, skup):
    """
    sum  - suma koju trazimo
    tren - trenutna suma
    skup - skup brojeva koji dolazi u obzir za sumiranje
    """
    
    for i in skup:
        lista.append(i)
        tren += i
        if tren == sum:
            insert(lista)
            lista.pop()
            return
        elif tren > sum:
            lista.pop()
            return
        else:
            komb(sum, tren, skup)
            tren -= i
            lista.pop()



if __name__ == '__main__':
    sum = 20
    skup = [1, 3, 4, 5, 10, 11, 15]
    komb(sum, 0, skup)
    print kombinacije
[ urosk @ 17.02.2005. 08:26 ] @
Da, resenje je slicno.
[ Genie_1984 @ 23.11.2009. 23:30 ] @
Ima li neko rešenje ovog problema ali u C-u?

[Ovu poruku je menjao Genie_1984 dana 24.11.2009. u 00:43 GMT+1]