Необходимо рассмотреть 2 ^ n-1 подмножества (не считайте пустой набор).
В среднем каждое из этих 2 ^ n подмножеств имеет O (n) элементов. Таким образом, вы решите n * 2 ^ n вычислений, чтобы решить проблему.
Возможны некоторые ускорения, но ничто не сможет обойти 2 ^ n.
Если абсолютный размер элементов невелик (и дискретен), вы можете начать таблицу, указав, достижима ли конкретная сумма или нет, и добавив элементы в эти «места» на вашей таблице.
Сначала составьте таблицу. Его диапазон будет от суммы всех отрицательных чисел до суммы всех положительных чисел. (Таким образом, вы не получите никаких сумм, выходящих за пределы таблицы.)
Затем отметьте «0» как достижимый.
Затем для каждого номера, для каждого достижимого номера в вашей таблице, добавьте номер. Так что, если ваш первый номер 2, пометьте «2» как достижимый. Затем, если вы получите -3, отметьте «-3» и «2-3 = -1» как достижимые. И так до тех пор, пока не закончатся номера. Каждая часть таблицы, помеченная как достижимая, действительно достижима; Вы добавили несколько номеров, чтобы попасть туда!