#prerequisites:
#python
#ipython
#networkx
#graphviz
#pygraphviz
from collections import Counter
import networkx as nx

def multiset2sum(bset,tsum,cycles=1):
    G=nx.DiGraph()  #acyclic directed graph to keep track of visited nodes
    root=(0,0,0)  #value,level,sum
    G.add_node(root,done=0) #done if not is visited and branched
    paths=0  #number of paths that sum up to tsum
    sets=set() #all paths explored
    while paths<cycles and len(list(n for n in G.nodes(data=True) if n[1]['done']==0))>0:
        for nd in [n for n,d in G.out_degree_iter() if d==0 and G.node[n]['done']==0]:
            pathsfine=True
            for p in list(nx.all_simple_paths(G,source=root,target=nd)):
                pathsfine=True
                pth=zip(*p)[0]  #extract all elements from path for data mungling
                pthc=tuple(Counter(sorted(pth)).iteritems())  #immutable count for each element in path
                if (not pthc in sets) and (nd[2]<=tsum):
                    sets.add(pthc)  #new path added to set of explored paths
                else:
                    pathsfine=False  #this path is bad, remove it
                    G.remove_edge(p[-2],nd)
                    for ndi in reversed(p): #backtrack until meets a branch
                        nbrs=G.predecessors(ndi)+G.successors(ndi)                       
                        if len(nbrs)<=1:
                            G.remove_node(ndi)    
                        else:
                            break
                    break
            if not pathsfine: continue
            if nd[2]==tsum: #path is complete, no children
                paths+=1
                G.node[nd]['done']=1
                continue
            for it1 in bset: #branching here
                newnode=(it1,nd[1]+1,nd[2]+it1)
                G.add_node(newnode,done=0)
                G.add_edge(nd,newnode)
            G.node[nd]['done']=1
    return G,sets

G,sets=multiset2sum([11,12,13],100,1000)

%matplotlib inline
import matplotlib.pyplot as plt
%config InlineBackend.figure_format='png'
plt.figure(figsize=(16,32))
pos=nx.graphviz_layout(G)
nx.draw(G,pos,data=True)
#nx.draw_networkx_nodes(G,pos)
nx.draw_networkx_labels(G,pos,data=True);

G.nodes(data=True)

ll=[]
for it in sets:
    l=list(it)
    ll.append((sum(a*b for a,b in l), l))
for l in sorted(ll,key=lambda x: x[0], reverse=True):
    print l