Динамическое программирование: идеальная сумма с отрицательными числами ⇐ JAVA

[Anonymous]

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

Код: Выделить всё

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]

Я сделал это, используя динамическое программирование за псевдополиномиальное время. Это расширение проблемы суммы подмножества, которое занимается только принятием решения о том, существует такое подмножество или нет. Мое решение ниже работает как для положительных, так и для отрицательных чисел в задаче о сумме подмножества. Однако она не может правильно распечатать подмножества, если массив содержит отрицательные числа. Программа-

Код: Выделить всё

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[i][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[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
else
subset[i][j] = subset[i - 1][j] || subset[i - 1][j + set[i - 1]];
}
}
}

// uncomment this code to print table
//        for (int i = 0; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/52399530/dynamic-programming-perfect-sum-with-negative-numbers[/url]