Поместить данные в вектор.
Затем напишите подпрограмму, которая имеет 3 аргумента: вектор, индекс и сумму.
Вызовите эту процедуру со следующими аргументами: вектор, 0, 0.
Подпрограмма должна выполнять следующие задачи:
- проверить, достиг ли мы конца вектора (индекс == размер). Если это так, мы можем немедленно вернуться.
- вызовите себя с аргументами: вектор, индекс + 1, сумма + вектор [индекс]
(в этом случае мы добавляем элемент с индексом к сумме и продолжаем с вектором)
- вызовите себя с аргументами: вектор, индекс + 1, сумма
(в этом случае мы не добавляем элемент с индексом к сумме, но все еще продолжаем)
Я намеренно пропустил 2 части в этом алгоритме:
- во-первых, вы должны проверить сумму в какой-то момент. Если это ноль, то вы нашли правильное подмножество
- во-вторых, вы также должны передать знания о том, какие элементы вы использовали, поэтому, если сумма равна нулю, вы можете распечатать подмножество. Рассмотрите возможность использования STL :: set для этого.
Кроме того, вы можете использовать возвращаемое значение функции, чтобы определить, было ли найдено правильное подмножество или нет.
Сложность алгоритма O (2 ^ N), поэтому он будет очень медленным для больших наборов.
Веселитесь.