algorithm - 在线性时间内将整数列表拆分为等和的子列表

Question

我找到了一种算法，可以通过以下方式做到这一点:

1. 给定列表 l，计算其和 s。
2. 计算下表:

(s,acc)

1. (s,0)

2. (s-x1,x1)

3. (s-x1-x2,x1+x2)

   ...

n. (s-x1-...x_n-1,x1+x2+...+x_n-1)

而在每一步中，您都检查该对的左侧元素是否等于第二个。

然后，此算法会在线性时间内确定您的列表是否可以拆分为两个子列表，以便每个子列表的总和相同。

我已经尝试了一段时间来正式证明这一点。但是，我开始认为这可能只对自然数有效，对整数无效。

1. 你能证实这个观点吗？
2. 你能给出一个算法来处理整数和线性复杂度吗？

编辑(我的解决方案到现在为止)

fun check_list :: "int list ⇒ int ⇒ int ⇒ bool" where
"check_list [] n acc = False" |
"check_list (x#xs) n acc = (if n = acc then True else (check_list xs (n-x) (acc+x)))"

fun linear_split :: "int list ⇒ bool" where
"linear_split [] = False" |
"linear_split [x] = False" |
"linear_split (x # xs) = check_list xs (sum_list xs) x" 

Answer 1

系统要求您将列表(按原样)分成两部分而不重新排序。

I've trying for a while to proof this formally.

您的算法是正确的，因为您基本上是通过沿列表移动分隔符来覆盖每一个可能的拆分:

 | O O O  split 1
 O | O O  split 2
 O O | O  split 3
 O O O |  split 4

Can you give an algorithm to do this for integers and for linear complexity?

您的算法也适用于整数。同样，因为您正在检查每个可能的解决方案并且它的复杂性是线性的，因为您只是在列表上迭代两次(第一次计算 sum)