返回信息流> 问题详细描述见附件；
简要描述为：
给定整数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``
最终的函数输出应该如下：
```JavaScript
countChange(4, [1,2]) // => 3
countChange(10, [5,2,3]) // => 4
countChange(11, [5,7]) // => 0
```
大概想了一下算法，和回溯差不多，先将M数组排序，从最小的M一步一步加上去，但是实现起来感觉很乱，希望大家能一起讨论！
这是一条镜像帖。来源：北邮人论坛 / java-script / #326同步于 2016/9/20
该镜像源已超过 30 天没有更新，可能在源站已被删除。
JavaScript机器人发帖
【算法讨论】codewars里的Counting Change Combinations问题
veah07
2016/9/20镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
# 你先别想着怎么加，可以反过来从减法入手...
> i.e. sum 和 arr = [a, b, c]
> f(sum, arr) = f(sum - a, [a, b, c]) + f(sum - a, [b, c])
也就是说最终的方法数是 sum - a 后继续减 a 的方法数 *【加上】*不再减 a 的方法数
计算过程中 sum 和 arr 的数量在不断地减少
* 当 sum 被减为 0 时，正好是一种方法
* 当 sum 小于 0 或 数组中没有元素了，就说明失败了
* 否则可以继续将 sum 的加法方法数分解成 (sum - arr[0], arr) + (sum - arr[0], arr.slice(1))
所以代码可以这样写...
```javascript
function reduce(sum, arr, num) {
if (sum === 0) return num + 1;
if (sum < 0 || !arr.length) return num;
return reduce(sum - arr[0], arr, num) + reduce(sum, arr.slice(1), num);
}
function countNum(sum, arr) {
if (sum <= 0 || !arr.length) return 0;
return reduce(sum, arr, 0);
}
```
ps，没必要排序，倒是需要数组去个重...
【 在 veah07 的大作中提到: 】
: [md]
: > 问题详细描述见附件；
: 简要描述为：
: ...................
我就想知道你跟楼上是什么关系哈哈哈
【 在 stevesasuke 的大作中提到: 】
: 其实用加的也一样...
: 只是比较的就是sum而不是比较方便的0了...～=￣ω￣=～
:
: 通过『我邮2.0』发布
: