获取数组 [1, 2 , 5, 9] 中所有和等于 20 的可能组合,允许重复。 就像:
5+5+5+5=20;
1+9+5+5=20;
9+9+2=20;
9+5+1+1+1+1+1+1=20
etc.
请给我一些提示,或者我可以在 google 中搜索的内容。
最佳答案
有很多可能的方法,这里是一个
- 取最大的第一个(9)
- 不断给自己添加,直到达到或超过目标(20)
- 要么将组合添加到您的接受列表中,要么不添加,具体取决于它是否符合您的目标
- 如果组合中的最后一个数字不是数组中最小的,则将最后一次迭代替换为下一个最大的数字并返回第 2 步
- 回到第一个数字链的末尾,用下一个最大的数字替换它
例如:
9+9+9 = 27
舍弃这个答案
用下一个最大的迭代替换上一次迭代,然后重复
9+9+5 = 23
舍弃这个答案
用下一个最大的迭代替换上一次迭代,然后重复
9+9+2 = 20
将此添加到您接受的组合列表
用下一个最大的迭代替换上一次迭代,然后重复
9+9+1+1 = 20
将此添加到您接受的组合列表
我们现在位于数组的末尾(不再有更小的数字)所以我们必须回到 9 链的末尾并将最后一个替换为下一个最小的并重复
9+5+5+5 = 24
舍弃这个答案
用下一个最大的迭代替换上一次迭代,然后重复
9+5+5+2 = 21
舍弃这个答案
用下一个最大的迭代替换上一次迭代,然后重复
9+5+5+1 = 20
等等……
关于algorithm - 在数组 [1, 2 , 5, 9] 中获取总和等于 20 的所有可能组合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40957285/