之前写的自我检讨v2上周，博文发现了硬币组合有几种——独特的子序列之和，并发表了关于硬币组合有几种的算法问题的解法。 算法本身可以给出正确答案，但仔细想想，并不能简单直接地解释为什么这样跑很有效。 好的算法应该可以用简单易懂的方法告诉别人，但是如果连制作这个算法问题的人都不能解释的话，就算这个算法能跑，也不是好的吧。
关于这个问题，有人给出了更好的解决方法，很容易理解。 听了之后，我真的对功绩之深不服啊~
问题和复制&； 如果有糊的分析硬币序列和表示其数量的序列，如何得到总共多少种不同组合的和？
例如，硬币数组[ 10，50，100 ]和表示其数量的数组[ 1，2，1 ]表示这里共有三种硬币，一枚10分，两枚50分，一枚100分。 可能的数组组合如下
10=3358 www.Sina.com/50=http://www.Sina.com/100=http://www.Sina.com/1050=http://www.Sina.com/10100=
从这里开始是认真分析的第一步。 把所有的硬币放在一个排列中首先，前面博文中的第一步和第二步是正确的。 我们确实需要把所有硬币组合起来，组成一个包含所有硬币的新排列coinList。 这个部分的代码将继续使用。
代码如下。
/* * count number of * @ param { array number } coinsarraycontainscoinswithdifferentvalues * @ param { array number } countsarraycontainscorrespondingcountsofdifferentcoins * @ returns { number } thecountofdistinctsums */functioncountdistion } const results={}； const coinList=[]； for(letI=0； i coins.length； I ) for(letj=0； j counts[i]； j ) (coinlist.push ) coins[I]； }//wherethebeautyofalgorithmshowsreturnobject.keys (results ).length - 1； //Remove the empty 0 coin element}第二步：了解所有组合是如何计算出来的我们一步一步，看看所有组合是如何得出的。 如果，现在我们只有一个硬币，一分。 可能性只有一种。 那是[1]。
现在增加一个硬币，变成2分。 可能性有[ 1，2，12 ]、3种。
再加一个硬币的话，会是三分吗？ 可能性有[1、2、3、12、13、23、123]、7种。
仔细看。 当硬币数量一个接一个地增加时，可能的组合数量也会相应地有规律地又增加。 什么规律？ 好像看不太清楚。 那么用别的方法表示吧？
硬币用a、b、c表示的话。
1枚硬币： a 1枚硬币时，如下所示。
a
两张硬币： A、b两张的时候呢？ 那么，在前面的a后面添加新的b
A B
此外，前面的a也应该是kkdmz
A B
a
加上新增加的b，结果如下
A B
a
B
三枚硬币： a、b、c此时追加了第三枚。 我们在前面三种情况下都加了C，就是
亚乙c
A C
B C
因为以前的三个组合还存在，所以整个数组
亚乙c
A C
B C
A B
a
B
最后加上新添加的c，最终得到了
亚乙c
A C
B + C
A + B
A
B
C
这下是否更清楚了？每当一个新的硬币被加进数组之中时，组合的数量始终是之前的两倍多一个。比如：
1枚硬币时，组合数量是1 2枚硬币时，组合数量是1 * 2 + 1 = 3 3枚硬币时，组合数量是3 * 2 + 1 = 7 4枚硬币时，组合数量是7 * 2 + 1 = 15......
以此类推
第三步：只储存非重复的值在计算过程中，难免会遇到许多重复的值。比如两枚硬币都是10分的时候，计算出来的组合是[10, 10, 20]。但其实我们不需要两个10，而只需要[10, 20]就可以了。这个时候我们需要用到Set这种数据结构来储存数据。因为set里面的元素都是非重复的。
比如，一组硬币[10, 50, 50]。处理第一枚硬币的时候，Set里有[10]。
处理第二枚硬币时，对这个Set里的所有元素提取出来并且加上新的硬币值，10 + 50得到了60，并添加得到的和与新添加的这枚硬币值进入进入Set里，得到了[10, 50, 60].
处理第三枚硬币时，还是继续提取出这个Set里的所有元素，并且加上新的硬币值。于是：
10 + 50 = 6050 + 50 = 10060 + 50 = 110将这三个新的和加入Set，去掉重复值之后得到了[10, 50, 60, 100, 110]。然后再把第三枚硬币本身的值，50，也添加进去。但因为50已经存在了，则Set还是[10, 50, 60, 100, 110]。
一直重复循环到最后，我们将得到所有非重复的和。问题至此也被解决了~
大功告成完整代码
/* * Count number of * @param {Array<Number>} coins array contains coins with different values * @param {Array<Number>} counts array contains corresponding counts of different coins * @returns {Number} The count of distinct sums */function countDistinctSum(coins, counts) { if(coins.length !== counts.length) { return -1; } const coinList = []; for(let i = 0; i < coins.length; i++){ for(let j = 0; j < counts[i]; j++) { coinList.push(coins[i]); } } // Create a new set const results = new Set(); for(let i = 0; i < coinList.length; i++){ // tempSum is used to store the temporary sum of every element in the set and new coin value const tempSum = []; for (let it = results.values(), val= null; val = it.next().value; ) { tempSum.push(val + coinList[i]); } // add every sum in tempSum to the set and the set will do automatic duplication removal. tempSum.forEach(n => { results.add(n); }); // add the new coin value into the set results.add(coinList[i]); } return results.size;}测试：
const a = [10, 50, 100];const b = [1, 2, 1];console.log('Result:', countDistinctSum(a, b)) // Result: 9