Подмножества данного набора целых чисел, сумма которых является константой N: Java

Question

Учитывая набор целых чисел, как найти подмножество, которое суммирует данное значение ... проблема подмножества?

Пример: S = {1,2,4,3,2,5} и n = 7 Нахождение возможных подмножеств, чья сумма равна n. Я пытался гуглить, нашел много ссылок, но не было понятно. Как мы можем решить это в Java, и какова структура данных, которая будет использоваться, и ее сложность?

Answer 1

В три этапа:

1. Найти набор параметров S (набор всех подмножеств S)

2. Вычислить сумму каждогоподмножество

3. Отфильтровать подмножества, которые не составили 7.

Answer 2

Я не дам вам никакого кода, но объясню, как он работает.

1. Запустите цикл из 0 to (2^k-1)
2. Для каждого значения в 1, 1 в двоичном представленииуказывает, что выбрано это значение, а в противном случае - 0.
3. Проверьте, равна ли сумма выбранных чисел n .

Приведенный выше метод оцениткаждое возможное подмножество данного набора.

Если верхний предел значений мал, то можно использовать подход динамического программирования.