问题描述如图;
简要描述为:
给定整数N和数组M[m1,m2,m3...],写出一个函数,算出所有由数组M中的数相加等于N的方式的数量。注意是方法的数量不是方法。例如,N=4,M=[1,2]。则用(1,2)一共有三种方式来构成4:
1+1+1+1, 1+1+2, 2+2。
数字相加的顺序并不重要:
1+1+2 == 2+1+1
最终的函数输出应该如下:
countChange(4, [1,2]) // => 3
countChange(10, [5,2,3]) // => 4
countChange(11, [5,7]) // => 0
大概想了一下算法,和回溯差不多,先将M数组排序,从最小的M一步一步加上去,但是实现起来感觉很乱,希望大家能一起讨论!
人生最曼妙的风景,竟是内心的淡定与从容!