Учитывая массив целых чисел и сумму, задача состоит в том, чтобы распечатать все подмножества заданного массива с суммой, равным данной сумме. < /p>
Example:
Input : arr[] = {1, 2, 3, 4, 5}
sum = 10
Output : [4 3 2 1]
[5 3 2]
[5 4 1]
Input : arr[] = {-1, 2, 3, 4, 5}
sum = 10
Output : [5 3 2]
[5 4 2 -1]
< /code>
Я сделал это с использованием динамического программирования в псевдономиальное время. Это расширение задачи подмножество SUM, которая только заботится о том, существует ли такое подмножество или нет. Мое решение ниже работает как для положительных, так и для отрицательных чисел для задачи подмножество SUM. Тем не менее, он не может правильно распечатать подмножества, если массив содержит отрицательные числа. Программа-< /p>
import java.util.ArrayList;
// sum problem
class GFG {
static boolean subset[][];
// Returns true if there is a subset of
// set[] with sun equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum) {
// The value of subset[j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
subset = new boolean[n + 1][sum + 1];
// Fill the subset table in botton
// up manner
for (int i = 0; i = 0)
subset[j] = subset[j] || subset[j - set];
else
subset[j] = subset[j] || subset[j + set];
}
}
}
// uncomment this code to print table
// for (int i = 0; i
Как можно изменить этот код для работы и для отрицательных чисел? < /p>
Подробнее здесь: https://stackoverflow.com/questions/523 ... ve-numbers
