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

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

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

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

比如：硬幣數(shù)組[10, 50, 100]，和代表其數(shù)量的數(shù)組[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

則，不重復(fù)的值則包括加黑的部分，一共是9個(gè)。

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

代碼如下：

/**
 * 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
}

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

現(xiàn)在我們?cè)黾右粋€(gè)硬幣，2分。則可能性則變成了[1, 2, 1+2]，3種。

如果我們?cè)偌右粋€(gè)硬幣，3分呢？則可能性又變成了[1, 2, 3, 1+2, 1+3，2+3，1+2+3]，7種。

仔細(xì)看，當(dāng)硬幣的數(shù)量一個(gè)一個(gè)地增加，可能的組合數(shù)量也相應(yīng)地有規(guī)律地再增加。什么規(guī)律？？？好像看不是很清楚。那么我們換一種方法來表示呢？

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

一枚硬幣的時(shí)候，是：
A

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

A + B

除此之外，之前的A也應(yīng)該在里面

A + B

A

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

A + B

A

B

這時(shí)候加第三枚了，我們?cè)谥暗倪@三種情況下都加上C，則變成了

A + B + C

A + C

B + C

而之前的那三種組合是還存在的，所以整個(gè)數(shù)組變成了

A + B + C

A + C

B + C

A + B

A

B

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

A + B + C

A + C

B + C

A + B

A

B

C

這下是否更清楚了？每當(dāng)一個(gè)新的硬幣被加進(jìn)數(shù)組之中時(shí)，組合的數(shù)量始終是之前的兩倍多一個(gè)。比如：

1枚硬幣時(shí)，組合數(shù)量是1

2枚硬幣時(shí)，組合數(shù)量是1 * 2 + 1 = 3

3枚硬幣時(shí)，組合數(shù)量是3 * 2 + 1 = 7

4枚硬幣時(shí)，組合數(shù)量是7 * 2 + 1 = 15

......

以此類推

在計(jì)算過程中，難免會(huì)遇到許多重復(fù)的值。比如兩枚硬幣都是10分的時(shí)候，計(jì)算出來的組合是[10, 10, 20]。但其實(shí)我們不需要兩個(gè)10，而只需要[10, 20]就可以了。這個(gè)時(shí)候我們需要用到Set這種數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存數(shù)據(jù)。因?yàn)?b>set里面的元素都是非重復(fù)的。

比如，一組硬幣[10, 50, 50]。處理第一枚硬幣的時(shí)候，Set里有[10]。

處理第二枚硬幣時(shí)，對(duì)這個(gè)Set里的所有元素提取出來并且加上新的硬幣值，10 + 50得到了60，并添加得到的和與新添加的這枚硬幣值進(jìn)入進(jìn)入Set里，得到了[10, 50, 60].

處理第三枚硬幣時(shí)，還是繼續(xù)提取出這個(gè)Set里的所有元素，并且加上新的硬幣值。于是：

10 + 50 = 60

50 + 50 = 100

60 + 50 = 110

將這三個(gè)新的和加入Set，去掉重復(fù)值之后得到了[10, 50, 60, 100, 110]。然后再把第三枚硬幣本身的值，50，也添加進(jìn)去。但因?yàn)?0已經(jīng)存在了，則Set還是[10, 50, 60, 100, 110]。

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

完整代碼

/*
 * 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