Способ наименьшей грубой силы посмотреть, сколько групп чисел в группе чисел добавляют к данному числу в C ++ или Python

Question

Название, вероятно, немного двусмысленно.

Существует заданное число.

Существует набор чисел, все меньше указанного числа и больше нуля.1006 * Я хочу знать, сколько существует различных комбинаций сложения чисел, равных данному числу.

Например, если заданное число равно 14, а числа в наборе 7, 7, 7, 6, 4 и 4. Было бы 4 комбинации.(7 + 7, 7 + 7, 7 + 7, 6 + 4 + 4)

Мне все равно, на каком языке находится решение, но я бы предпочел C ++ или Python.

Answer 1

Не падайте духом утверждениями, что это NP-полная.В статье Википедии о сумме подмножеств, связанной @isbadawi, упоминается статья профессора Дэвида Пизингера 1999 года с алгоритмом, который звучит так, как будто он будет работать с вашими существующими ограничениями в линейном времени: http://www.sciencedirect.com/science/article/pii/S0196677499910349.Это $ 31,50, но это звучит как сделка, если вам действительно нужно хорошо решить эту проблему.