Sum of Subset of an Array equals a given number

Let's start with a subtle bug in your code:

unsigned long two_pow_n = 1 << n; 

According to the problem description, n is at most 20, so using unsigned long is good, an int is only guaranteed to have 16 bits according to the C standard. But 1 is an int and if n exceeds the number of bits in an int then the behaviour of 1 << n is undefined. So

• Either you know that int has (at least) 32 bit on your platform. Then you don't need to use long at all.

• Or you don't want to make that assumption: Then it must be

  unsigned long two_pow_n = 1UL << n; 

  using an unsigned long int literal.

Now some remarks to your current implementation. First, I would put the computation into its own function and separate it from the I/O:

bool hasSubsetSum(unsigned numbers[], unsigned n, unsigned targetSum) { // ... return true or false } 

That makes the program structure more organized, and allows to add test cases easily. I have used bool from <stdbool.h>. If that is not available with your compiler, replace it by int.

Next, your code to update the teller array looks a bit obfuscated to me. Actually you don't need that array at all: You already test all bit positions of j in

if (j % (1 << k) == 0) { ... 

so you can use the same test to update either sum1 or sum0.

You compute both a sum and a complementary sum at once, which is a good idea to cut the (maximal) number of iterations into half. But the loop

for (j = 0; j < two_pow_n; ++j) 

does not reflect that, you only need to iterate over 2^(n-1) combinations.

Finally, a variable should be declared at the narrowest possible scope. In particular, loop variables should be declared in the loop statement:

for (unsigned int j = 0; j < two_pow_n; ++j) 

Putting it all together, you code could look like this:

bool hasSubsetSum(unsigned numbers[], unsigned n, unsigned targetSum) { unsigned long two_pow_n1 = 1UL << (n - 1); for (unsigned long j = 0; j < two_pow_n1; ++j) { unsigned sum0 = 0, sum1 = 0; for (unsigned k = 0; k < n; ++k) { if ((j & (1UL << k)) == 0) { sum0 += numbers[k]; if (sum0 == targetSum) { return true; } } else { sum1 += numbers[k]; if (sum1 == targetSum) { return true; } } } } return false; } 

Alternatively you could compute the totalSum of all numbers in advance and then compare both sum1 and totalSum - sum1 with the target sum.

This should be a bit faster than your original approach, but it is still the "brute-force" algorithm to solve the "subset sum problem" and has complexity O(2^n).

For positive integers (as in your case) there is a better algorithm using "dynamic programming". The rough idea is to incrementally compute a list of all sums which are achievable with the given numbers, and then check if the target sum is in that list.

One possible implementation is to use a boolean array hasSum with indices from 0 up to targetSum. Initially, only hasSum[0] is true. Then for each number x in the given array and all possible indices j in hasSum, hasSum[j + x] is set to true if hasSum[j] == true.

Here is a sample implementation of that algorithm:

bool hasSubsetSum(unsigned numbers[], unsigned n, unsigned targetSum) { bool hasSum[targetSum + 1]; for (unsigned i = 0; i <= targetSum; ++i) { hasSum[i] = false; } hasSum[0] = true; unsigned maxIndex = 0; // Highest index in `hasSum` which is `true` // For all numbers in the given array ... for (unsigned k = 0; k <= n; ++k) { // For all `j` for which `hasSum[j] == true` ... for (unsigned j = maxIndex; j != (unsigned)(-1); --j) { if (hasSum[j]) { unsigned sum = j + numbers[k]; // New achievable sum if (sum == targetSum) { return true; } else if (sum < targetSum) { hasSum[sum] = true; if (sum > maxIndex) { maxIndex = sum; } } } } } return false; } 

The inner loop is traversed in decreasing order, so that updating the boolean array does not influence the computation for the current number[k].