# Sum of Subset of an Array equals a given number

Posted on

Problem

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 <stdio.h>

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

unsigned int note[n];
unsigned long j;

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

char teller[n], flag = 0;

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

unsigned long two_pow_n = 1 << n;

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

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

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

flag ? printf("Yesn") : printf("Non");
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!

Solution

``````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]`.

This is a classical Dynamic Programming problem. I suggest you going through the topic first.DP. This link is very useful but you can google it as well.Just one advice, DP is not an easy topic to understand and more importantly to implement. We all struggle there. But after you have an idea what is DP, understand 0-1 Knapsack problem. After that i think all your doubts will be cleared.

i also submitted my code on codechef for this problem. you can have a look at it also.

``````import java.io.*;

public class Main
{
public static void main(String[] args) throws IOException
{
String[] str = null;
while(t-- > 0)
{
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
int[] arr = new int[n];
for(int i = 0 ; i < n ; i++)
{
}
func(arr,n,m);
}
}

public static void func(int[] arr,int n ,int m)
{
int[][] mat = new int[n + 1][m + 1];
for(int i = 0 ; i < n + 1 ; i++)
{
mat[i][0] = 1;
}
for(int i = 1 ; i < n + 1 ; i++)
{
for(int j = 1 ; j < m + 1 ; j++)
{
if(j < arr[i - 1])
{
mat[i][j] = mat[i - 1][j];
}
else if(j == arr[i - 1])
{
mat[i][j] = 1;
}
else
{
if(mat[i - 1][j] == 1)
{
mat[i][j] = 1;
}
else
{
if(mat[i - 1][j - arr[i - 1]] == 1)
{
mat[i][j] = 1;
}
else
mat[i][j] = 0;
}
}
if(j == m && mat[i][j] == 1)
{
System.out.println("Yes");
return;
}
}
}
System.out.println("No");
}
}
``````