# 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 <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("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!

• Your solution is in the order of O(2^n) which makes it unusable for large calculations. On Codechef, you can look at other's solutions, so I suggest have a look at some others like this one: codechef.com/viewsolution/990854. Jun 11, 2017 at 7:57
• @TheRandomGuy Yeah I looked at various solutions, but wasn't able to understand their algorithm. I think the one you linked uses recursion.. Jun 11, 2017 at 8:04
• This is the well known "subset sum problem". For positive integers it can be solved with dynamic programming. See e.g. geeksforgeeks.org/dynamic-programming-subset-sum-problem or stackoverflow.com/questions/4355955/subset-sum-algorithm or youtube.com/watch?v=s6FhG--P7z0. Jun 11, 2017 at 9:14
• Actually I am pretty new to programming and don't understand dynamic programming. I'll try to understand from that link. Jun 11, 2017 at 10:06

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

• Many thanks for your answer, I am going through it now, will update if I have a doubt! regarding the number of loop comparisons, yes I forgot to make that 2^(n-1). Jun 11, 2017 at 15:42

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);
int m = Integer.parseInt(str);
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] = 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");
}
}