Sum of Subset of an Array equals a given number

Question

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!

Answer 1

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

Answer 2

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");
    }
}