def preglej_v_globino(x, sosedi, resitev):
    """Preišči vse možnosti v globino.
       Pri tem je x začetno stanje, sosedi je funkcija, ki vrne
       sosede danega stanja (in se ne ponavljajo), predikat
       resitev pa pove, ali smo nasli rešitev."""

    def pregled(y):
        if resitev(y):
            return y
        else:
            for z in sosedi(y):
                r = pregled(z)
                if r is not None: return r
            return None

    return pregled(x)

# Primer: vsota podmnožice
def vsota_podmnozice_globina(s, n):
    # Stanje: (s, n, t) kjer je s seznam števil, ki so na razpolago,
    # n je razlika do ciljne vsote in t do sedaj zgrajena rešitev

    def f(st):
        """"Funkcija, ki izračuna naslednje stanje"""
        (s,n,t) = st
        if len(s) == 0:
            return []
        else:
            x = s[0]
            r = s[1:]
            return [(r, n - x, t + [x]), (r, n, t)]

    return preglej_v_globino((s, n, []), f, (lambda st: st[1] == 0))[2]

print (vsota_podmnozice_globina([1,2,3,4,5], 12))

def pregled_v_sirino(x, sosedi, resitev):
    """Preišči vse možnosti v širino.
       Pri tem je x začetno stanje, sosedi je funkcija, ki vrne
       sosede danega stanja (in se ne ponavljajo), predikat
       resitev pa pove, ali smo nasli rešitev."""

    vrsta = [x] # seznam stanj, ki jih moramo še pregledati
    while len(vrsta) > 0:
        y = vrsta.pop(0) # vzamemo prvega iz vrste
        if resitev(y):
            return y
        else:
            vrsta.extend(sosedi(y))
    return None

# Primer: vsota podmnožice
def vsota_podmnozice_sirina(s0, n0):
    # Stanje: (s, n, t) kjer je s seznam števil, ki so na razpolago, n ciljno število in t do sedaj zgrajena rešitev

    def f(st):
        """"Funkcija, ki izračuna naslednje stanje"""
        (s,n,t) = st
        if len(s) == 0:
            return []
        else:
            x = s[0]
            r = s[1:]
            return [(r, n - x, t + [x]), (r, n, t)]

    return pregled_v_sirino((s0, n0, []), f, (lambda st: st[1] == 0))[2]