摘要：寫在前面的自我檢討上周我發布了一篇博文有多少種硬幣組合找出獨特子數組之和，是關于有多少種硬幣組合的算法題的解法。假如，現在我們只有一個硬幣，分。則可能性只有種，那就是。

上周我發布了一篇博文有多少種硬幣組合——找出獨特子數組之和，是關于有多少種硬幣組合的算法題的解法。雖然算法本身能夠給出一個正確答案，可是仔細想來，我卻沒辦法給出一個簡單直接的解釋為什么這樣跑可以奏效。好的算法應該是能夠以一種通俗易懂的方法教給別人的，如果連做出這道算法題的人都無法解釋清楚，那即便這個算法能夠跑起來，也不能算好吧。

就這個問題，一位高人給出了一個更好的解決方式，通俗易懂。聽完之后，我真是不得不服功力之高深吶~

如果你有一個硬幣數組和一個代表其數量的數組，如何得到一共有多少種不同組合所得的和？

比如：硬幣數組[10, 50, 100]，和代表其數量的數組[1, 2, 1]就表示這里一共有三種硬幣，1枚10分，2枚50分和1枚100分硬幣。那么其可能的排列組合則包括

10 = 10

50 = 50

100 = 100

10 + 50 = 60

10 + 100 = 110

50 + 50 = 100

50 + 100 = 150

10 + 50 + 50 = 110

10 + 50 + 100 = 160

50 + 50 + 100 = 200

10 + 50 + 50 + 100 = 210

則，不重復的值則包括加黑的部分，一共是9個。

首先，上一篇博文里的第一步和第二步是正確的，我們確實需要將所有硬幣組合起來，組成一個新的數組coinList，其中包含了所有的硬幣。則這部分的代碼還是繼續使用。

代碼如下：

/**
 * Count number of 
 * @param {Array} coins array contains coins with different values
 * @param {Array} 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 results = {};
    const coinList = [];

    for(let i = 0; i < coins.length; i++){
        for(let j = 0; j < counts[i]; j++) {
            coinList.push(coins[i]);
        }
    }

    // where the beauty of algorithm shows

    return Object.keys(results).length - 1; // Remove the empty 0 coin element
}

我們一步一步來看，所有的組合是如何的出來的。假如，現在我們只有一個硬幣，1分。則可能性只有1種，那就是[1]。

現在我們增加一個硬幣，2分。則可能性則變成了[1, 2, 1+2]，3種。

如果我們再加一個硬幣，3分呢？則可能性又變成了[1, 2, 3, 1+2, 1+3，2+3，1+2+3]，7種。

仔細看，當硬幣的數量一個一個地增加，可能的組合數量也相應地有規律地再增加。什么規律？？？好像看不是很清楚。那么我們換一種方法來表示呢？

如果將硬幣表示為A, B, C。

一枚硬幣的時候，是：
A

兩枚硬幣的時候呢？那我們直接在之前的A后面加上一枚新的B

A + B

除此之外，之前的A也應該在里面

A + B

A

再加上新增加的B，則變成了：

A + B

A

B

這時候加第三枚了，我們在之前的這三種情況下都加上C，則變成了

A + B + C

A + C

B + C

而之前的那三種組合是還存在的，所以整個數組變成了

A + B + C

A + C

B + C

A + B

A

B

最后加上新增加的C，最終得到了

A + B + 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 = 60

50 + 50 = 100

60 + 50 = 110

將這三個新的和加入Set，去掉重復值之后得到了[10, 50, 60, 100, 110]。然后再把第三枚硬幣本身的值，50，也添加進去。但因為50已經存在了，則Set還是[10, 50, 60, 100, 110]。

一直重復循環到最后，我們將得到所有非重復的和。問題至此也被解決了~

完整代碼

/*
 * Count number of
 * @param {Array} coins array contains coins with different values
 * @param {Array} 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