## Counting Problems

**Problem 1: Given a set of n numbers a_{i} sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to K?**

Also called the **Subset Sum Problem**, in this problem, the number of times we can use a particular number is limited i.e. we can use a number only once. This problem can be done in two ways

1> Binary Representation of Numbers and

2> DP

**1> Using Binary Representation of Numbers**

First lets discuss the common approach for iterating through all subsets of a set. Mathematics tells us that the total number of subsets of a set is *2*^{n}. THe easier way to do this is in any programmin language is to represent each element of a set by a single bit of the number. So for example, if we have 3 elements in a set then we have 8 subsets. or we can iterate from 0 to 7 to get all subsets as

Number | Binary Representation |

0 | 000 |

1 | 001 |

2 | 010 |

3 | 011 |

4 | 100 |

5 | 101 |

6 | 110 |

7 | 111 |

So if we let 1 in the binary represent that the number is selected and 0 that the number is not selected, we actually have all the subsets of the set. We can use this approach to solve the above problem by iterating through all subsets and finding whether the sum is equal to the required sum. The point to be noted is that this approach is quite slow since for a worst case scenario we iterate through all the *2*^{n} cases. Also checking each bit takes time. Here’s a simple C++ implementation of the above logic. Below is a program which takes as input N numbers and M the required subset sum and outputs Yes if the subset sum M is possible and No otherwise.

int a[21]; int main() { int t,N,M,i,j,k,sum; bool F; scanf("%d",&t); while(t--) { scanf("%d%d",&N,&M); for (i=0;i<N;i++) scanf("%d",&a[i]); F=0; j=1<<N; for (i=1;i<j && F==0;i++) { sum=0; for (k=0;k<N;k++) { if ((i & (1<<k)) == (1<<k)) sum += a[k]; } if (sum == M) { F=1; printf("Yes\n"); } } if (F==0) printf("No\n"); } }

The time complexity of the above code is O(*2*^{n}). We also have a O(*2*^{n/2}) algorithm, where we divide the input numbers into two equal subsets. Then we calculate the sum of subsets of each of the two subset. We then iterate through the sums of one subset and check whether M-sum is present in the sums of the other subset. If yes, we get our desired result. If there are no such values we print no.

#include<iostream> using namespace std; #include<set> int a[21]; int main() { int t,N,M,i,j,k,sum,x; set<int> s1,s2; set<int>::iterator l; scanf("%d",&t); while(t--) { scanf("%d%d",&N,&M); s1.clear(); s2.clear(); for (i=0;i<N;i++) scanf("%d",&a[i]); j=1<<(N/2); for (i=0;i<j;i++) { sum=0; for (k=0;k<N/2;k++) { if ((i & (1<<k)) == (1<<k)) sum += a[k]; } s1.insert(sum); } x=N-N/2; j=1<<x; for (i=0;i<j;i++) { sum=0; for (k=0;k<x;k++) { if ((i & (1<<k)) == (1<<k)) sum += a[k+N/2]; } s2.insert(sum); } for (l=s1.begin();l!=s1.end();l++) { if (binary_search(s2.begin(),s2.end(),M-*l)) { printf("Yes\n"); break; } } if (l==s1.end()) printf("No\n"); } }

**2> DP Approach**

This is the other approach to solving this problem. This method takes into account that the possible sum’s after including a number, are all previous possible sum’s plus the new number. So we only check whether x-*a*_{i} is a possible sum, if yes x is also a possible sum. We iterate from M (maximum possible sum) to *a*_{i} because we cannot include a number twice. Here’s the C++ implementation of the above program using DP approach.

int m[30000],a[21]; int main() { int t,N,M,i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&N,&M); for (i=0;i<N;i++) scanf("%d",&a[i]); for (i=0;i<=M;i++) m[i]=0; m[0]=1; for(i=0; i<N; i++) for(j=M; j>=a[i]; j--) m[j] |= m[j-a[i]]; if (m[M]) printf("Yes\n"); else printf("No\n"); } }

**Problem 2: Given that the a_{i}‘s are unlimited i.e you can use the numbers in the subset as many times as you want find whether a particular sum M is possible and if possible how many ways are there to do it?**

Also called the **Counting Change Problem**, this problem is a variation of the above problem and we just need to change the direction of the second loop in the above problem. Here’s a program to find the number of ways to change a amount of Rs. 100 using the coins and notes of RS. 1,2,5,10,20,50,100.

int main() { int coin[7]={1,2,5,10,20,50,100},i,j,x,c; x=100; vector<long long> ways(x+1,0); ways[0]=1; for (i=0;i<7;i++) { c=coin[i]; for (j=c;j<=x;j++) ways[j]+=ways[j-c]; } cout<<ways[100]<<endl; }

More variations of the above problem can be minimizing the number of elements required to get a particular sum.

**Problem 3: Find the number of ways of writing a number as the sum of positive integers?**

Also called the **Partition Function** P of n, it is denoted by *P(n)*. For example,

5 | 5 |

4+1 | |

3+2 | |

3+1+1 | |

2+2+1 | |

2+1+1+1 | |

1+1+1+1+1 |

Euler invented a generating function which gives rise to a recurrence equation in *P(n)*,

Below is a program to calculate *P(n)*. It can easily modified to include large numbers.

#include<iostream> using namespace std; #include<map> map <int , long long> P; long long Calculate_Pn(long long n) { if (n < 0) return 0; long long Pn = P[n]; if (Pn == 0) { long long k; for (k = 1; k <= n; k++) { // A little bit of recursion long long n1 = n - k * (3 * k - 1) / 2; long long n2 = n - k * (3 * k + 1) / 2; long long Pn1 = Calculate_Pn(n1); long long Pn2 = Calculate_Pn(n2); // elements are alternately added // and subtracted if (k % 2 == 1) Pn = Pn + Pn1 + Pn2; else Pn = Pn - Pn1 - Pn2; } P[n]=Pn; } return Pn; } int main() { long long i; P[0]=1; while (scanf("%lld",&i)!=EOF) printf("%lld\n",Calculate_Pn(i)); }

Happy Coding!!!

-fR0D

There is also a O(2^(n/2)) algorithm which uses binary search or data structures like balanced trees 🙂

Check it out on wikipedia, it’s good when the numbers are too large to permit a DP.

whomeSeptember 24, 2009 at 12:34 AM

hey buddy..

regarding the DP approach to counting problem,

if the statement goes like this…

“Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to K, the subset of numbers must contain x elements where x<M?"

i.e in this case, the number of elements required to obtain the sum K are given, then how to go about this problem.

ayanJanuary 23, 2010 at 10:38 AM

I don’t know of any DP approach that can be used to do this. The subset should contain exactly x elements or the number of elements in the subset be less than equal to x?

fR0DDYJanuary 25, 2010 at 9:10 PM

the number of elements should be exactly equal to x.

ayanJanuary 25, 2010 at 9:38 PM

Then I am unaware of a solution. If i do get to know any, I will let you know. Also can you give me the source of the question?

fR0DDYJanuary 25, 2010 at 9:41 PM

thanks anywayz… 🙂

this is a question from UVA ..

problem no: 10032

ayanJanuary 25, 2010 at 9:49 PM

[…] problema. References: 1. Wikipwdia 2. Introduction to Algorithms, Thomas h: Cormen, MIT Press 3. https://comeoncodeon.wordpress.com/2009/07/21/counting-problem/ Possibly related posts: (automatically generated)Euler Problem 278Euler Problem 99Project Euler i […]

Subset Sum Problem « Bahrudin Hrnjica BlogMarch 23, 2010 at 11:19 PM

Curiously I’ve developed an algorithm for solving subset sum problems using natural numbers, and this uses an abstract form of counting to form rules on how to progress the search of possible subsets. So for the nCr type problem of a target of 2 for the set { 1, 1, 1, 1 } my algorithm, without any special cases, will progress to the binary solutions as follows:

0011

0101

0110

1001

1010

1100

The algorithm for this case would also never select more than 2 numbers from the original set. In fact for any problem it is possible to determine the maximum and minimum subset sizes it would possibly consider. Currently I’m developing an application that uses the algorithm to find non intersecting subset sums from a set, and it behaves in a similar manner for these cases. To the best of my knowledge, (endless google searches), the technique has not been published, or made public by anybody else.

JB

John BuftonApril 17, 2010 at 7:30 AM

Hi John,

This is not a new algorithm but a known one. In fact, the question asked above by Ayan

“Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to K, the subset of numbers must contain x elements where x<M?"

has to be solved by a similar algorithm.

fR0DDYApril 17, 2010 at 4:30 PM

[…] problema. References: 1. Wikipwdia 2. Introduction to Algorithms, Thomas h: Cormen, MIT Press 3. https://comeoncodeon.wordpress.com/2009/07/21/counting-problem/ Share/Bookmark This entry was posted in C#, Programiranje, Project Euler and tagged C#, Project […]

Subset Sum Problem | Bahrudin Hrnjica BlogDecember 25, 2010 at 1:00 AM

Greetings ..

My name is Ahmad, I just wanted to thank you very much for this code, Ive been trying to do such a function but unfortunately it didnt work out.

anyway Im participating in the ACM local contest and I hope I can refer to you and ask you anything.

many thanks in advance.

best regards.

Ahmad

AhmadOctober 27, 2011 at 5:45 AM

Sure.

fR0DDYOctober 27, 2011 at 9:49 AM

solution to subset_sum problem:-

1> Using Binary Representation of Numbers

in the given code what is – “t”??

Thanks in advance

addiNovember 23, 2011 at 10:50 AM

t is number of test cases, it is not related to the problem at hand.

fR0DDYNovember 23, 2011 at 10:58 AM

Hi ,

for Counting Change Problem when i=0

for (j=c;j<=x;j++)

ways[j]+=ways[j-c];

then this loop will make ways[100]=100;

i didnt get this bcoz ways[100] represents number of ways by which we can use given coin to sum upto Rs 100

so when i=0 then Rs 1 is selected and it is making value of ways[100]=100 i.e there are 100 ways by which you can sum up to 100 using Rs 1 coin….. I doubt that

coin Rs 1 can be added 100 times to make 100 Rs..this is 1 way of doing it not 100 ways..

please let me know where i am making mistake.

Thanks in advance 🙂

addiNovember 24, 2011 at 10:06 AM

When i = 0, then we have all the values for ways equal to zero except ways[0]. So we get a loop for j from 1 to 100 and ways[1] = ways[0] = 1. Then ways[2] = ways[1] = 1 and so on till ways[100] = ways[99] = 1. So there is only one way to make a sum of 100 by using 1 Re coins.

fR0DDYNovember 24, 2011 at 10:38 AM

Thanks fRoDDY …got it

sorry my mistake , i didnt read the code properly

addiNovember 24, 2011 at 12:39 PM

Variant of coins-change!

=)

How about this:

Determine if there is a way to give a change R using at most k coins.

Example:

The coins are this: v1 = 1; v2 = 5; v3 = 10.

We have to give change R = 17.

We must use k = 4 coins.

So, the solution is R = 1 + 1 + 5 + 10 (because of the 4 coins k)

(If R = 18, for example above, there is no way!)

CarmelinaJune 29, 2015 at 9:22 PM