algorithm - 你如何找到 N 个整数，使得它们的总和等于 M？

Question

你如何找到 N 个不同整数的任何可能组合，使得它们的总和等于给定的整数 M？

整数可以在 -2^31 到 2^31 之间，N 小于或等于 500000，M 也在 -2^31 到 2^31 之间。

一个例子：

• 4 表示为 N，8 表示为 M。
• 可能的组合是 3, -1, 4, 2

标签： algorithmcombinations

Answer 1

假设N是奇怪的。我们可以选择N/2不是 M 的正整数。我们也可以选择那些整数的负数。最后，我们选择M。例如，如果N = 5和M = 9，我们可以选择2, -2, 4, -4。然后我们简单地选择9，作为我们的最终整数，给我们一个总和M。

假设N是偶数。我们可以使用类似的系统，但选择N/2-1正整数和负整数，0然后M。所以对于N = 6, M = 11, 我们可以选择5, -5, 6, -6, 0, 11总和11。

这些选择不是唯一的，但简单地选择连续的整数是微不足道的。