algorithm - 拆分具有约束的子集

Question

今天，在练习一些算法题时，我发现了一个有趣的问题。问题是

You have to divide 1 to n (with one missing value x ) into two equal halfs such that sum of the two halfs are equal.

Example:

If n = 7 and x = 4

The solution will be {7, 5} and {1, 2, 3, 6}

我可以用蛮力法回答，但我想要一个有效的解决方案谁能帮帮我？

Answer 1

如果没有 x 的元素 1→N 的和是奇数则无解。

否则，您可以通过平衡选择在 O(N) 中找到您的解决方案。

连续4个

首先让我们考虑一下，任何四个连续数字的序列都可以分成两个总和相等的集合:

[x, x+1, x+2, x+3] → [x+3, x];[x+2, x+1]

因此选择它们并将它们放入集合 A B B A 平衡集合 A 和 B。

4横跨

此外，当我们有两对跨越一个省略值时，它可以拥有一个相似的属性:

[x-2, x-1, x+1, x+2] → [x+2, x-2]; [x+1, x-1]

还是A B B A

此时我们可以修复以下情况:

• 我们有一个四胞胎:我们将其拆分为案例 1
• 我们有 2 个数字，x 和其他 2 个数字:我们按照情况 2 拆分

好吧，但我们可能有 3 个数字，x 和其他 3 个数字，或其他条件。无论如何，我们如何才能平衡地进行选择？

+2差距

如果我们再看看 x 上的差距:

[x-1, x+1]

我们可以注意到，如果我们将两个邻居分成两个单独的集合，我们必须以某种方式平衡集合上的 +2 和更大的总和。

平衡尾部

我们可以通过使用序列的最后四个数字来做到这一点:

[4 3 2 1] → [4, 2] ; [3, 1] → 6 ; 4

最后我们不得不考虑我们可能没有其中一个，所以让我们构建另一个案例:

[3 2 1] → [2] ; [3, 1] → 2 ; 4

让我们也意识到我们可以在序列的另一端用 A B A B(或 B A B A)模式做同样的事情——如果我们的 +2 站在 B(或 A)上；

4跨+

令人惊奇的是，如果我们跳 h(奇数!)个数字，跨度 4 仍然成立:

[x+3, x+2, x-2, x-3] → [x+3, x-3]; [x+2, x-2]

因此，探索数组我们可以逐步得出解决方案

一个例子:

11 10 9 8 7 6 5 4 3 2 1

和是偶数，所以x只能是偶数:

x = 10
11 - 9 | 8 7 6 5 | 4 3 2 1 → (+2 gap - on A) (4 in a row) (balancing tail)
 A   B   A B B A   B A B A

x = 8
11 10 | 9 - 7 | 6 5 | 4 3 2 1 → (4 across +) (+2 gap - on A) (balancing tail)
 a  b   A   B | b a | B A B A

x = 6
11 10 9 8 | 7 - 5 | 4 3 2 1 → (4 in a row) (+2 gap - on A) (balancing tail)
 A  B B A   A   B   A B B B

x = 4 we have no balancing tail - we have to do that with head
11 10 9 8 | 7 6 | 5 - 3 | 2 1 → (balancing head) (4 across +) (+2 gap)
 A  B A B   A B | b   a | B A

x = 2
11 10 9 8 | 7 6 5 4 | 3 - 1 → (balancing head) (4 in a row) (+2 gap)
 A  B A B   A B B A   B   A

注意解的对称性很有趣。另一个例子。

10 9 8 7 6 5 4 3 2 1

和是奇数，所以x只能是奇数，现在元素个数是奇数。

x = 9
10 - 8 | 7 6 5 4 | 3 2 1 → (+2 gap - on A) (4 in a row) (balancing tail)
 A   B   A B B A   B A B

x = 7
10 9 | 8 - 6 | 5 4 | 3 2 1 → (4 across +) (+2 gap - on A) (balancing tail)
 a b | A   B | b a   B A B

x = 5
10 9 8 7 | 6 - 4 | 3 2 1 → (4 in a row) (+2 gap - on A) (balancing tail)
 A B B A   A   B   B A B

x = 3
10 9 8 7 | 6 5 | 4 - 2 | 1 → (balancing head) (4 across + virtual 0) (+2 gap)
 A B A B   B A | a   b | A

x = 1
10 9 8 7 | 6 5 4 3 | 2 → (balancing head) (4 in a row) (+2 gap virtual 0)
 A B A B   A B B A   B 

最后值得注意的是，只要我们有一个完整的平衡段(即连续 4 个或跨 4 个)，我们就可以从 A 切换到 B

有趣的是 - 但如果您自己尝试，要求 sum([1 ... N]-x) 为偶数的属性会使这些情况变得非常多余。

---

我很确定这个算法可以推广 - 我可能会很快提供一个修订版本。