C++

Forum

 
Subset sum problem with negative integers

jres (2)
Take a set A with n_A members. The problem is then to find out whether or not a subset of set A can sum to equal a target. This is a variation of the subset sum problem, with the exception that set A can also include negative integers. In this case, the negative integers involved are just negations of the positive integers, if that is any help.

The relevant code snippet I'm using is posted below. It works fine when the members of set A are positive, but gives wrong answers when negative integers are involved. What am I doing wrong? I do not get any errors.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
bool SubSum(vector <int> A, int n_A, int target)
{
if (target == 0) return true;
if ((n_A == 0) && (target != 0)) return false;

if (A[n_A-1]>0)
{
    if (A[n_A - 1] > target) return SubSum(A, n_A - 1, target);
    return SubSum(A, n_A - 1, target) || SubSum(A, n_A - 1, target - A[n_A - 1]);
}
else
{
    if (A[n_A - 1] < target) return SubSum(A, n_A - 1, target);
    return SubSum(A, n_A - 1, target) || SubSum(A, n_A - 1, target - A[n_A - 1]);
};

Last edited on
helios (17523)
On line 6 you use a_n, which doesn't appear anywhere else in the snippet.
jres (2)
I meant n_A. Post updated.
helios (17523)
It seems to me that this algorithm will give false negatives even with only positive inputs, since you're only searching for continuous runs of items from the start of the vector to some point in the middle. For example, there exists a subset in [1, 2, 3, 4] that adds up to 4, but none of [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]] add up to 4.
Topic archived. No new replies allowed.