Как найти все возможные суммы и разности чисел в векторе?

Question

Предположим, у меня есть вектор, называемый числами. Номера = {1, 5, 6, 8}. (Возможность у меня есть хотя это удвоить размер вектора и включают в себя все отрицательные числа, но я до сих пор не имеют хорошее решение, чтобы найти все возможные суммы.)

Возможные решения:

4 = 5 - 1

1 = 1

19 = 8 + 6 + 5

Я хочу, чтобы остановить поиск, когда я нашел номер я буду искать, но моя главная проблема заключается в том, чтобы найти все разные суммы.

Это очень похоже на проблему суммирования подмножества, но я действительно не нашел решение, которое я могу понять/включая отрицательные числа.

Answer 1

Использование динамического программирования.

Позвольте (a_0, ..., a_{n-1}) быть вашим массивом чисел. Позвольте A(k) быть множеством всех возможных сумм/разниц (a_0, ..., a_{k-1}). Тогда вы можете легко вывести A(k) от A(k-1). Убедитесь, что все повторения удалены, используя хеш-таблицу или сортировку или что-то еще.

Дело в том, что, если есть верхняя граница m из a_i-х, то A(k) содержит не более 2mk + 1 элементов. Таким образом, сложность снижается с O(3^n) до примерно O(mn^2).

Это, наверное, самое лучшее, что вы можете сделать: например, если экспоненциально увеличиваются значения a_i, то размер конечного результата также экспоненциальный.

Answer 2

Подумайте о тройном представлении {0, 1, 2}, у вас есть набор чисел, где каждое число может отображаться как положительное, отрицательное или не отображаемое, тогда вы можете представить эту возможность как тройную {0, 1, 2} и использовать его с coef -> {-1, 0, 1}, вы можете легко вычислить все комбинации. coef -> (-1, 0, 1) -> тернарный '0' -> значение '-1', тройной '1' -> значение '0' и тройной 2 -> значение '1'.

Numbers -> {n0, n1, n2, .. ni}

троичной представление ->(t0)*3^0 + (t1)*3^1 + (t2)*3^2 + .. + (ti)*3^i

Коэф ->{c0 , c1, c2, .. ci}

Результат ->C0*n0 + C1*n1 + C2*n2 + .. + Ci*ni

Пример:

Numbers = {1, 5, 6, 8}

Всего комбинаций ->3^4 = 81

номер комбинации (c) ∈ ​​[0, 80].

f.е: c = 79 ->2221(ternary)

троичный (реверс) {1, 2, 2, 2} к коэф {0, 1, 1, 1}

результат (79d/2221t): 0*1 + 1*5 + 1*6 + 1*8 = 19

Чтобы вычислить все возможные комбинации, вы должны рассчитать эти шаги в цикле (i -> 0 .. 3^4)