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
inthas (at least) 32 bit on your platform. Then
you don’t need to uselongat 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 intliteral.
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");
}
}