这是关于分区问题的算法面试问题。
您将得到一个数组，该数组由介于0到5位之间的数字组成。编写一个函数，该函数将返回是否可以将数组分为两半，以使两半之和相等。
这是NP问题还是可以通过动态编程解决？
我认为“ 0到5位数之间”表示0〜99999。
我在这里在外面找到了一个很好的答案。
都。问题出在NP上，我很确定可以通过动态编程在伪多项式时间内解决它。
http://en.wikipedia.org/wiki/Partition_problem
一般问题是NP完全问题，可以通过动态编程在伪多项式时间内解决。Ť
对于0-5位数字的这种特定限制可能不是NP完整的。什么是0位数数字？
通常，对于分区问题，不需要分区大小相等，只要它们具有相等的总和即可。但是在这里您说“分为2个一半”，我不确定“一半”是指数组的一半，还是仅意味着总数的一半。
我猜想这种差异（如果是差异）可能不会影响DP解决方案的复杂性，但是我不确定。我没有任何一种临时证明，而且，“嗯，看起来就像您可以使用DP进行的事情，我必须考虑一下”。
