有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))