Zhiyue · 纸岳
HomeAbout

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

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 分硬币。那么其可能的排列组合则包括

  1. 10 = 10
  2. 50 = 50
  3. 100 = 100
  4. 10 + 50 = 60
  5. 10 + 100 = 110
  6. 50 + 50 = 100
  7. 50 + 100 = 150
  8. 10 + 50 + 50 = 110
  9. 10 + 50 + 100 = 160
  10. 50 + 50 + 100 = 200
  11. 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]就有以下排列方法。

  1. [10]
  2. [10, 50]
  3. [10, 100]
  4. [10, 50, 100]
  5. [50]
  6. [50, 100]
  7. [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<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

Written by Yi Zhiyue A Software Engineer · 山不在高,有仙则灵
LinkedIn · GitHub · Email