How to implement the subset sum problem algorithm?

Question

Algorithms

Given a set of real numbers N. The problem is to find (one is enough) a subset of N so that the sum of the numbers of this subset is equal to S. The numbers can be negative, and they can also be repeated.
I tried to solve it by enumeration, but the number of numbers is quite large (330 pieces) and in this century I will not have time to count. Saw solutions with dynamic programming but they either don't support negative numbers or they don't support repeating numbers. I don't know what to do
ps The numbers in the set N can be repeated. example N = {1, 1, 2, 5}

Answer 1

It is not necessary to look for the optimal (shortest) set that gives the desired amount?
I propose to move from simple to complex:

check each pair of numbers from Nfor the difference: if there is a difference of 1, you can get any number through these two

check each triple of numbers from NThe subtask is the same, get 1. If there is 1, there is any integer.

Answer 2

Negative numbers, of course, spoil the problem a lot;) classical search algorithms do not have such a trick.
But it makes sense to keep the general logic: your goal is a certain amount, you can strive for it. At each selection step, the options are sorted by how much their addition brings you closer to the desired amount (modulo). And iterate until the first number gives a difference of 0.

Answer 3

Google is not lucky to ask? The problem of the sum of subsets
ps By the way, information about computational complexity comes first

Answer 4

Normal dynamic programming works for repeating numbers, there shouldn't be a problem. Negative numbers are solved simply - consider all possible sums of only positive numbers as standard dynamics and separately only for negative numbers (omitting the sign). Then, in one cycle, iterate over the sum of positive numbers x>=S and see if xS can be typed with negative numbers. This cycle does not affect the overall complexity.