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

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

最近因為一些原因，做了幾道“簡單”的算法題。今天要講的便是其中的一道題：如果你有一個硬幣數組和一個代表其數量的數組，如何得到一共有多少種不同組合所得的和？

比如：硬幣數組[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個。

而我們現在的問題便是，輸入兩個數組：硬幣數組和代表其數量的數組，得到一個整數的返回值。

根據分析，函數的輸入與輸出應該規定如下。

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

首先，我們應該先做一個檢查，如果coins的長度跟counts的長度并不相等的話，則函數不應該繼續處理，而是應該返回一個錯誤值。暫且定為-1吧。

然后，我們采用key value pair的形式來儲存不同和（sum）的數量。所以我們必須有一個名叫result的對象。當然，其中并沒有任何的key。在函數運行必要的計算之后，再返回result的key的數量作為最后的答案。

另外，我們還需要將所有硬幣組合起來，組成一個新的數組coinList，其中包含了所有的硬幣。比如：硬幣數組[10, 50, 100]，和代表其數量的數組[1, 2, 1]，組合成[10, 50, 50, 100]。這一部分用兩個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
}

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

[10]

[10, 50]

[10, 100]

[10, 50, 100]

[50]

[50, 100]

[100]

這時，我便考慮使用遞歸法（recursive method）來解決這個問題。

函數接受兩個輸入

results用來儲存已經有的sum

n用來儲存硬幣數組的長度

sum用來儲存臨時已經疊加的和

currentIndex用來記錄當前遍歷到的索引

coinList用來輸入當下數組里的硬幣元素。

設置出口條件

當currentIndex大于coinList的長度時，返回。

當currentIndex等于coinList的長度時，調用addToResults函數（下一步講解）然后返回。

遞歸函數

processList()會被遞歸兩次，這兩者之間的帶入參數區別只有sum的不同而已

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

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

代碼如下：

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

因為result本身是空的，當我們算出一個和是result里沒有的key的話，必須初始化這個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;
    }
}

測試：

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

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