Todas as combinações de um conjunto #backtrack #combinatory

todascombinacoes.py

def imprime(letras, vet, lst):
    s = ''
    for x in xrange(len(letras)):
        if vet[x] == True:
            s += letras[x]
    lst.append(s)

def combinacoes(letras, vet, p, n, lst):

    if p == n:
        imprime(letras, vet, lst)
    else:
        k = p
        vet[k] = False
        combinacoes(letras,vet, p + 1, n, lst)
        vet[k] = True
        combinacoes(letras, vet, p + 1, n, lst)

if __name__ == '__main__':
    lst = []
    letras = ['a', 'b', 'c', 'd']
    vet = [ False, False, False, False]
    combinacoes(letras, vet, 0, len(letras), lst)
    print lst