这是算法面试问题：

您将得到一个数组，由   用介于0和5位数字。   写的函数，这将返回该阵列是否可划分   成两半这样的的那笔   两半会是平等的。

You are given an array which consists of numbers with between 0 and 5 digits. Write a function which will return whether the array can be divided into 2 halves such a that sum of the two halves would be equal.

这是一个NP问题，还是可以通过动态规划来解决？

Is this an NP problem or can it be solved by dynamic programming?

编辑：

0到5的数字范围是指0〜99999，我想。

"0 to 5 digit range" means 0 ~ 99999, I think.

我发现一个很好的答案这个分区的问题

推荐答案

两者。问题是在NP，我pretty的确保它可以在伪多项式时间动态规划来解决。

Both. The problem is in NP, and I'm pretty sure it can be solved in pseudo-polynomial time with dynamic programming.

http://en.wikipedia.org/wiki/Partition_problem

的一般问题是NP完全，并且可以在伪多项式时间与动态规划来解决。牛逼

The general problem is NP-complete, and can be solved in psuedo-polynomial time with dynamic programming. T

的它这特定的限制至0-5位号码可能不是NP完全问题。什么是0位数字，反正？

This specific restriction of it to numbers of 0-5 digits probably isn't NP-complete. What's a 0-digit number, anyway?

通常的划分问题没有要求的分区大小相同，只是他们有平等的总和。但在这里你说分为2个半，我不知道半是否是指一半的阵列，或者只是意味着总数的一半。

Usually for the partition problem there is no requirement that the partitions be of equal size, just that they have equal sum. But here you say "divided into 2 half", I'm not sure whether "half" is intended to mean half the array, or just to mean half the total.

我猜这种差异，如果是有区别的，可能不会影响该DP解决方案的复杂性，但我不知道。我没有证明任何一种方式了手，超越，嗯，是啊，看起来像那种你可以用DP做的事，我得想想。

I'd guess that this difference, if it is a difference, probably doesn't affect the complexity of the DP solution, but I'm not sure. I don't have a proof either way off-hand, beyond, "um, yeah, looks like the kind of thing you can do with DP, I'd have to think about it".