Subset sum with negative numbers

user_6937598 0
Viewed 4067

So I have a given set C of n positive integers (c_1, ..., c_n). The task is to find two subsets A and B of C, where A contains only positive numbers and B contains only the negatives of the numbers in C. The sum of the two subsets A and B should then sum up to a number d (d is always positive). I need to find out whether there are two such subsets and if so, which numbers do they contain.

For example: {3, 5, 6, 13, 24} // d = 12 => solution: true: {5, 13} {-6}

I know this is a variation of the subset sum problem and I've seen some solutions for a similar problem (subset sum with negative numbers) but I need to solve the problem using dynamic programming. Most solutions I've seen work with recursion, not with DP.

I think I need a 3D boolean table S(i,j,k) with size (n * n * d). But when is S(i,j,k) true and when false? Because I'd always need to check all the possible ways to compute a sum using k number where they can be both positive and negative (example: for 4 numbers {1,2,3,4} there are 2^4 ways to arrange them: 1 + 2 + 3 + 4, 1 - 2 + 3 + 4, 1 - 2 - 3 + 4, ..., -1 + 2 - 3 - 4, 1 - 2 - 3 - 4)

Is my thinking correct or am I already doing something wrong?

subset-sum dynamic-programming algorithm java
1 Answers

One approach is to use the standard dynamic programming subset sum algorithm on a set consisting of (c_1,c_2,...,c_n,-c_1,-c_2,...,-c_n).

This will find a subset that sums to d (or prove that none exists).

Set A to all the positive numbers in the subset, and B to all the negative numbers.

You may also wish to remove any numbers that appears in both A and B (e.g. if you have a 3 in A and -3 in B then you can remove both without changing the sum).

user_11393930
Related