查找总和在阵列等于零 [英] Find sum in array equal to zero

问题描述

由于整数数组，找出一组至少有一个整数概括为0。

Given an array of integers, find a set of at least one integer which sums to 0.

例如，由于 [ - 1，8，6，7，2，1，-2，-5] ，该算法可以输出 [ - 1，6,2，-2，-5] 因为这是输入阵列，它概括为0的一个子集

For example, given [-1, 8, 6, 7, 2, 1, -2, -5], the algorithm may output [-1, 6, 2, -2, -5] because this is a subset of the input array, which sums to 0.

该解决方案必须在多项式时间内运行。

The solution must run in polynomial time.

推荐答案

您将有一个很难在多项式时间内这样做，因为这个问题是被称为的子集和问题，并已知的 NP完全。

You'll have a hard time doing this in polynomial time, as the problem is known as the Subset sum problem, and is known to be NP-complete.

如果你找到一个多项式的解决方案，但是，你已经解决了 P = NP？的问题，这将让你相当丰富的。

If you do find a polynomial solution, though, you'll have solved the "P = NP?" problem, which will make you quite rich.

你到一个已知的多项式的解决方案最接近的是一个近似值，如在维基百科中列出的，这将努力让你一个答案了一笔接近，但不一定等于0。

The closest you get to a known polynomial solution is an approximation, such as the one listed on Wikipedia, which will try to get you an answer with a sum close to, but not necessarily equal to, 0.

这篇关于查找总和在阵列等于零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！