有多少种硬币组合——找出独特子数组之和
October 25, 2018
写在前面的自我检讨
这道题的解法，刚开始我自己做的并不算是一个很好的解法，只能说题目是做出来了，但过程中的计算有大量的重复计算，导致函数复杂度直逼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<Number>} coins array contains coins with different values
* @param {Array<Number>} 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
当我们得到一个 coinList 之后，接下来我们便要处理这个数组，将其内部的元素全都排列一遍。比如，[10, 50, 100]就有以下排列方法。
[10][10, 50][10, 100][10, 50, 100][50][50, 100][100]
这时，我便考虑使用递归法（recursive method）来解决这个问题。
-
函数接受两个输入
results用来储存已经有的 sumn用来储存硬币数组的长度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<Number>} 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);
}
第四步 addToResults 函数
因为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<Number>} coins array contains coins with different values
* @param {Array<Number>} 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<Number>} 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