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

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

.

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
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
String[] str = null;
while(t-- > 0)
{
str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
int[] arr = new int[n];
for(int i = 0 ; i < n ; i++)
{
arr[i] = Integer.parseInt(br.readLine());
}
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");
}
}
```