有多少种硬币组合——找出独特子数组之和

摘要：另外，我们还需要将所有硬币组合起来，组成一个新的数组，其中包含了所有的硬币。比如硬币数组，和代表其数量的数组，组合成。

这道题的解法，刚开始我自己做的并不算是一个很好的解法，只能说题目是做出来了，但过程中的计算有大量的重复计算，导致函数复杂度直逼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