摘要：另外，我們還需要將所有硬幣組合起來，組成一個(gè)新的數(shù)組，其中包含了所有的硬幣。比如硬幣數(shù)組，和代表其數(shù)量的數(shù)組，組合成。

這道題的解法，剛開始我自己做的并不算是一個(gè)很好的解法，只能說題目是做出來了，但過程中的計(jì)算有大量的重復(fù)計(jì)算，導(dǎo)致函數(shù)復(fù)雜度直逼O(n^n)。查閱資料之后便有了一個(gè)改良版。感謝這篇文章Find all distinct subset (or subsequence) sums of an array!

最近因?yàn)橐恍┰?，做了幾道“?jiǎn)單”的算法題。今天要講的便是其中的一道題：如果你有一個(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è)。

而我們現(xiàn)在的問題便是，輸入兩個(gè)數(shù)組：硬幣數(shù)組和代表其數(shù)量的數(shù)組，得到一個(gè)整數(shù)的返回值。

根據(jù)分析，函數(shù)的輸入與輸出應(yīng)該規(guī)定如下。

/**
 * 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) {
    // Implementation
}

首先，我們應(yīng)該先做一個(gè)檢查，如果coins的長(zhǎng)度跟counts的長(zhǎng)度并不相等的話，則函數(shù)不應(yīng)該繼續(xù)處理，而是應(yīng)該返回一個(gè)錯(cuò)誤值。暫且定為-1吧。

然后，我們采用key value pair的形式來儲(chǔ)存不同和（sum）的數(shù)量。所以我們必須有一個(gè)名叫result的對(duì)象。當(dāng)然，其中并沒有任何的key。在函數(shù)運(yùn)行必要的計(jì)算之后，再返回result的key的數(shù)量作為最后的答案。

另外，我們還需要將所有硬幣組合起來，組成一個(gè)新的數(shù)組coinList，其中包含了所有的硬幣。比如：硬幣數(shù)組[10, 50, 100]，和代表其數(shù)量的數(shù)組[1, 2, 1]，組合成[10, 50, 50, 100]。這一部分用兩個(gè)for loop輕松搞定。

代碼如下：

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]);
        }
    }

    processList(coinList, coinList.length, 0, 0, results);

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

當(dāng)我們得到一個(gè)coinList之后，接下來我們便要處理這個(gè)數(shù)組，將其內(nèi)部的元素全都排列一遍。比如，[10, 50, 100]就有以下排列方法。

[10]

[10, 50]

[10, 100]

[10, 50, 100]

[50]

[50, 100]

[100]

這時(shí)，我便考慮使用遞歸法（recursive method）來解決這個(gè)問題。

函數(shù)接受兩個(gè)輸入

results用來儲(chǔ)存已經(jīng)有的sum

n用來儲(chǔ)存硬幣數(shù)組的長(zhǎng)度

sum用來儲(chǔ)存臨時(shí)已經(jīng)疊加的和

currentIndex用來記錄當(dāng)前遍歷到的索引

coinList用來輸入當(dāng)下數(shù)組里的硬幣元素。

設(shè)置出口條件

當(dāng)currentIndex大于coinList的長(zhǎng)度時(shí)，返回。

當(dāng)currentIndex等于coinList的長(zhǎng)度時(shí)，調(diào)用addToResults函數(shù)（下一步講解）然后返回。

遞歸函數(shù)

processList()會(huì)被遞歸兩次，這兩者之間的帶入?yún)?shù)區(qū)別只有sum的不同而已

第一個(gè)processList()將帶入sum加上當(dāng)下的coin值，達(dá)到計(jì)算累計(jì)的效果。比如：[10, 50, 50, 100]一路加到最后成為210。

第二個(gè)processList()將之帶入當(dāng)下的sum值去到下一個(gè)遞歸。隨著index的增加，該sum值會(huì)將一直被保留直到最終被加入result，它也將實(shí)現(xiàn)跳躍相加的方法。比如：[10, 50, 50, 100]其中的10 + 100就可以在這個(gè)遞歸中實(shí)現(xiàn)。

代碼如下：

/**
 * Recursive function to collect all the sums from all combinations
 * @param {Array} coinList array of coins
 * @param {Number} n the length of coin array
 * @param {Number} sum the current accumulated value
 * @param {Number} currentIndex the current processing index in the coin array
 * @param {Object} results existing result object brought into recursive function for recording sum
 */
function processList(coinList, n, sum, currentIndex, results) {
    if(currentIndex > n) {
        return;
    }

    if(currentIndex === n){
        addToResults(results, sum);
        return;
    }

    processList(coinList, n, sum + coinList[currentIndex], currentIndex + 1, results);
    processList(coinList, n, sum, currentIndex + 1, results);
}

因?yàn)?b>result本身是空的，當(dāng)我們算出一個(gè)和是result里沒有的key的話，必須初始化這個(gè)key，使其值為1。反之，則只需要在其值上加1便可。

代碼如下：

/**
 * Add the number to results as a key
 * @param {Object} results 
 * @param {Number} number 
 */
function addToResults(results, number) {
    if(results[number]) {
        results[number]++;
    } else {
        results[number] = 1;
    }
}

完整代碼：

/**
 * 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]);
        }
    }

    processList(coinList, coinList.length, 0, 0, results);

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

/**
 * Recursive function to collect all the sums from all combinations
 * @param {Array} coinList array of coins
 * @param {Number} n the length of coin array
 * @param {Number} sum the current accumulated value
 * @param {Number} currentIndex the current processing index in the coin array
 * @param {Object} results existing result object brought into recursive function for recording sum
 */
function processList(coinList, n, sum, currentIndex, results) {
    if(currentIndex > n) {
        return;
    }

    if(currentIndex === n){
        addToResults(results, sum);
        return;
    }

    processList(coinList, n, sum + coinList[currentIndex], currentIndex + 1, results);
    processList(coinList, n, sum, currentIndex + 1, results);
}

/**
 * Add the number to results as a key
 * @param {Object} results 
 * @param {Number} number 
 */
function addToResults(results, number) {
    if(results[number]) {
        results[number]++;
    } else {
        results[number] = 1;
    }
}

測(cè)試：

const a = [10, 50, 100];
const b = [1, 2, 1];

console.log("Result:", countDistinctSum(a, b)) // Result: 9