有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？¶
输入整数n.(1<=n<=100000)输出组合数，答案对1e9+7取模利用回溯法进行求解，但是当n很大时，存在递归栈太深问题，可以满足n小数情形
num = input()num = int(num)# 回溯法def findNum(num):curSum = 0result = []item = []count = findNum_n(curSum+1, num, item + [1], result) + findNum_n(curSum+2, num, item + [2], result) +\findNum_n(curSum+5, num, item + [5], result) + findNum_n(curSum+10, num, item + [10], result)return count%(1e9+7)def findNum_n(curSum, num, item, result):if curSum == num:item.sort()if item not in result:result.append(item)return 1return 0if curSum > num:return 0return findNum_n(curSum+1, num, item + [1], result) + findNum_n(curSum+2, num, item + [2], result) +\findNum_n(curSum+5, num, item + [5], result) + findNum_n(curSum+10, num, item + [10], result)print(findNum(num))
