subset sum with negative values in c or c++

Question

I have this code for finding the subset sum of positive values and everywhere I searched I only see positive integers or a program written in java in advanced level. I want to know how to implement that my C program would work with negative numbers. Actually, I want it to find sum that is 0. I had an idea

1. Take the minimum value in the set, call it k.
2. Add each element in the set by the absolute value of k.
3. Add sum by the absolute value of k.
4. Perform the algorithm.

---

But I found that this wont work. Take the set (-5, 10) and see if any subset adds up to 5. We would convert (-5, 10) -> (0, 15) and 5->10. -5+10=5, but 0+15 != 10

---

A lot of ideas I searched on the internet but can't find the answer.

#include <stdio.h>

typedef int bool;
#define true 1
#define false 0

bool isSubsetSum(int set[], int n, int sum) {
    // Base Cases
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;

    if (set[n - 1] > sum)
        return isSubsetSum(set, n - 1, sum);

    return isSubsetSum(set, n - 1, sum) ||
           isSubsetSum(set, n - 1, sum - set[n - 1]);
}

int main() {
    int set[] = { -3, 34, -2, 12, 5, 8 };
    int sum = 0;
    int i;
    int n = sizeof(set) / sizeof(set[0]);
    if (isSubsetSum(set, n, sum) == true)
        printf("Found a subset");
    else
        printf("No subset");
    return 0;
}

Answer 1

I dont really understand your strategy. You should not use the absolute value. The sum of a+b has little to do with the sum of |a|+|b| (well there are some relations, but if you use them somewhere then I missed it ;).

If you have an algorithm that can find you a subset among positive integers that adds up to x, then you can use it also for negative numbers. It wont be as efficient, but with a small trick it can work....

First you add an offset to all numbers to make them all positive. Now you look for subsets that add up to x+y*offset, where y is the size of the subset. Eg. you have

A = -1, -3, -2, 6 12, 48

and you are looking for a subset that adds up to 0, then you first add 3 to all numbers,

b = 2, 0, 1, 9, 15, 51

and then try to find a subset of size 1 that adds up to 3, a subset of size 2 that adds up to 6, ...., a subset of size 4 that adds up to 12, that would be

12 = 2+0+1+9    ie    0 = -1 + -3 + -2 + 6

Doing it that way isnt very efficient, because you have to apply the algorithm N-times (N= size of input). However, if your algorithm for positives lets you fix the size of the subset, this may compensate this loss in efficiency.

Answer 2

I guess you can try a brute force attempt by removing the test for overflow:

#include <stdio.h>

int isSubsetSum(int set[], int n, int sum, int empty_ok) {
    // Base Cases
    if (sum == 0 && empty_ok)
        return 1;

    if (n == 0)
        return 0;

    return isSubsetSum(set, n - 1, sum, empty_ok) ||
           isSubsetSum(set, n - 1, sum - set[n - 1], 1);
}

int main(void) {
    int set[] = { 3, 34, 2, 12, 5, 8 };
    int n = sizeof(set) / sizeof(set[0]);
    int sum = 6;

    if (isSubsetSum(set, n, sum, 0) == true)
        printf("Found a subset");
    else
        printf("No subset");
    return 0;
}

Unfortunately, the time complexity of this solution is O(2ⁿ).

Here is a non recursive solution for sets up to 64 elements:

int isSubsetSum(int set[], int n, int sum) {
    unsigned long long last;

    if (n == 0)
        return sum == 0;

    last = ((1ULL << (n - 1)) << 1) - 1;

    // only find non empty subsets for a 0 sum
    for (unsigned long long bits = 1;; bits++) {
         int s = 0;
         for (int i = 0; i < n; i++) {
             s += set[i] * ((bits >> i) & 1);
         }
         if (s == sum)
             return 1;
         if (bits == last)
             return 0;
    }
}

Explanation: type unsigned long long is guaranteed to have at least 64 value bits. bits varies from 1 to last inclusive and takes all possible bit patterns of n bits except all off. For each value of bits, I sum the elements for which the corresponding bit is set, hence all possible non empty subsets are tested.

Answer 3

Code has TBD bug

Yet OP requested it to remain. I fix it later or take down tomorrow.

---

OP's code has trouble because it is searching for the wrong sum.

By finding the minimum value and offsetting each element of set[], the problem becomes one of only positive numbers - which apparently OP has solved prior.

The trick is that the target sum needs to be offset by n*offset

#include <stdio.h>
#include <stdbool.h>
//typedef int bool;
//#define true 1
//#define false 0

bool isSubsetSum(int set[], int n, int sum, int offset) {
    // Base Cases
    if ((sum  + n*offset) == 0)
        return true;
    if (n == 0 && (sum  + n*offset) != 0)
        return false;

    if (set[n - 1] > sum + n*offset)
        return isSubsetSum(set, n - 1, sum, offset);

    return isSubsetSum(set, n - 1, sum, offset) ||
           isSubsetSum(set, n - 1, sum - set[n - 1], offset);
}

int main() {
    int set[] = { -3, 34, -2, 12, 5, 8 };
    int sum = 0;
    int i;
    int n = sizeof(set) / sizeof(set[0]);
    int min = -3;  // TBD code to find minimum
    for (i = 0; i<6; i++) set[i] -= min;

    if (isSubsetSum(set, n, sum, -min) == true)
        printf("Found a subset");
    else
        printf("No subset");
    return 0;
}

---

Found a subset