Если «хорошо» означает «правильно», тогда просто попробуйте все возможности.Это займет у вас n choose m
времени.Очень медленно.К сожалению, это лучшее, что вы можете сделать в целом, потому что для любого набора целых чисел вы всегда можете добавить еще одно, которое является отрицательным от суммы m-1
других - и все остальные могут иметь одинаковый знак, поэтомуу вас нет возможности искать.
Если «хорошо» означает «быстро и обычно работает нормально», то есть несколько способов продолжить.Например:
Предположим, что вы можете решить задачу для m=2
, и предположим, что в дальнейшем вы сможете решить ее как для положительного, так и для отрицательного ответа (а затем возьмите меньшее из двух).Теперь предположим, что вы хотите решить m=4
.Решите для m=2
, затем выкиньте эти два числа и решите снова ... должно быть очевидно, что делать дальше!А как насчет m=6
?
Теперь предположим, что вы можете решить проблему для m=3
и m=2
.Думаю, что вы можете получить достойный ответ для m=5
?
Наконец, обратите внимание, что если вы сортируете числа, вы можете решить для m=2
за один проход, а для m=3
у вас раздражает квадратичный поискчтобы сделать, но, по крайней мере, вы можете сделать это только около четверти списка дважды (маленькие половины положительных и отрицательных чисел) и искать номер противоположного знака для отмены.