def noofSums(n,S,currDict):

  if n==0:
    target=0
    Pstring=""
    for key in currDict:
      if currDict[key]!=0:
        Pstring = Pstring + str(key) + "*" + str(currDict[key]) + " + "
        target = target+key*currDict[key]
    Pstring = Pstring[:-3]
    print Pstring, "=", target
    return 1
  elif n<0:
    return 0

  if len(S)==0:
    return 0

  Scopy = S.copy()
  trial = Scopy.pop()
  ret_value = 0

  for i in range(0,n/trial+1):
    currDict[trial]=i
    ret_value = ret_value + noofSums(n-i*trial,Scopy,currDict)
    del currDict[trial]
  return ret_value

if __name__ == '__main__':
  S={1,2,3}
  n=10
  print n, S
  result = noofSums(n,S,dict())
  print "Total combination ", result