Sum of Subset of an Array equals a given number The exact question that I am solving is given here:  Codechef - MARCHA1

Problem Statement

Basically, we have an array of n integers, say {1, 5, 6, 3, 12} where n = 5.  

Then we have a given number m = 10, and we have to check if the sum of any subset of the array is equal to m or not.  

In this case, we have 1+6+3 = 10, so we print Yes.

Proposed Solution

I proposed the following solution:

We create another array of n integers which only hold either 0 or 1. For example, in the case with n = 5, we can have this new array as {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0} .. etc

In this manner, each time we check for the sum of numbers of original array which are at position 1. So there are 2^n such cases.

After checking, if none of them match, we print No, else we print Yes.

Here's the code in C:

#include &lt;stdio.h&gt;

int main()
{
    unsigned int n, m;
    scanf("%u%u", &amp;n, &amp;m);

    unsigned int note[n];
    unsigned long j;

    for (j = 0; j &lt; n; ++j) {
        scanf("%u", note+j);
    }

    char teller[n], flag = 0;

    for (j = 0; j &lt; n; ++j) {
        teller[j] = 0;
    }

    unsigned long two_pow_n = 1 &lt;&lt; n;

    for (j = 0; j &lt; two_pow_n; ++j)
    {
        unsigned int sum0 = 0, sum1 = 0, k;

        for (k = 0; k &lt; n; ++k)
        {
            if (teller[k] == 0) {
                sum0 += note[k];
            }
            else {
                sum1 += note[k];
            }
            if (j % (1 &lt;&lt; k) == 0) {
                teller[k] = teller[k] == 0 ? 1 : 0;// swap 0 and 1
            }
        }

        if (sum0 == m || sum1 == m)
        {
            flag = 1;
            break;
        }
    }

    flag ? printf("Yes\n") : printf("No\n");
    return 0;
}


The problem with this approach is that it took too much time and too many comparisons. On the codechef website, I found my solution was among the slowest.

Please help me by suggesting a better algorithm, I couldn't think of any optimisation either. Thank you!
Let's start with a subtle bug in your code:

unsigned long two_pow_n = 1 &lt;&lt; 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 &lt;&lt; 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 &lt;&lt; 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 &lt;stdbool.h&gt;. 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 &lt;&lt; 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 &lt; 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 &lt; 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 &lt;&lt; (n - 1);

    for (unsigned long j = 0; j &lt; two_pow_n1; ++j) {
        unsigned sum0 = 0, sum1 = 0;
        for (unsigned k = 0; k &lt; n; ++k) {
            if ((j &amp; (1UL &lt;&lt; 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 &lt;= 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 &lt;= 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 &lt; targetSum) {
                    hasSum[sum] = true;
                    if (sum &gt; 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].