# Dynamic Programming: Combination Sum Problem

In this article, I present an alternative solution to a well-known "how many coins form a dollar" problem. The approach takes dynamic programming into use, which is known to solve problems of changing states. Typical problems of dynamic programming include fibonacci and factorials—the ones that involve recursion as their first choice of techniques.

### Problem Statement

Find out all combinations of coins 1, 5, 25, and 50 cents that form a dollar. A popular version of this problem also involves a dime (10 cents). This article tries to emphasize the concept involved: the role of Dynamic Programming. At the end, it is easy to see that solution is extendable to any number of coins that form a desired sum.

In mathematical jargon, you have N coins with values V1, V2, ..., VN and you need to obtain all the combinations that form your desired sum S with the help of one or more of these coins, combined or one at a time.

### Manual Approach

In the case of the dollar problem, it is not impossible to figure out the solution manually. With pen and paper, you can start deriving it like this:

1. How many ways 1s, 5s, 25s, or 50s can form a 100, taken one at a time: You need 100 1s, 20 5s, 4 25s, or 2 50s.
2. How many ways 1s and 5s can form a 100: You need to try from 1 to 19 5s and figure out how many 1s would be required to make the rest to get a hundred.
3. Similarly, how many ways 5s and 25s, 25s and 50s, 1s and 25s, 1s and 50s, can form 100.
4. The number of ways how 100 can be obtained from three coins. From Steps 2 and 3 above, you know all the double coin combinations that form a 100. For example, put all 1s and 5s that form a 100 on one side. Now, make them form a 75, instead of 100. As you guessed it, simply append a 25. and you got one combination.

Make them form a 50, append 2 25s, and you have the second three-coin combination, and so on. To understand, look at these calculations:

 1 5 95 1 = 100 2 5 90 1 = 100 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19 5 5 1 = 100 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 1 5 14 5 = 75 + 1 25 = 100 1 5 9 5 = 50 + 2 25 = 100

Once you have all the ways that three coins can form a sum, it is not hard to repeat the same process for the forth coin. Simply repeat what you did in Step 4 above, with three-coin combinations already arrived at to begin with, and append the fourth coin to every combination.

You begin getting tired after writing it all, but with careful and repetitive efforts, the correct solution can be arrived at, although I do not recommend it. The reason? Simply adding one more coin VN+1 (a dime that I purposefully omitted!) to the problem will make it an Olympic-sized task. Dynamic programming is here to solve exactly this type of problem. Although you are only demonstrating the approach with four coin values, you will see that attempting it with a considerably larger number of coins does not make it extremely complex. Also, the algorithm is much more efficient with higher coin values compared to the brute force approach, which you will also examine at the end.

### The DP Approach: A Formula?

Dynamic Programming tries to identify states and the conditions that change them. All you need is a function that relates an integer n with n - 1 (or its nearest relative, depending on the nature of problem).

A famous example of a DP solution is factorial, where through recursion you arrive at the solution one number at a time.

In case of factorial, the function is:

 F (n) = n*f (n - 1) if n>1 = 1 If n = 1

Try to get something like this for your problem. The coin problem requires you to get a sum S from V1, V2, ..., VN coins. You can define it as this:

`S = aV1 + bV2 + cV3 + ... + kVN`

You need to find a, b, c,...,k and present them along with V1, V2,...,VN as a combination solution.

### State Identification and Transition

Because you want to proceed step-by-step in DP, and the manual approach stated earlier already gives you some hints, try to build from the ground up. You always can arrive at a given sum from two values (coins). The algorithm goes something like this:

```For i = 1 to Sum / V1
For j = 1 to Sum / V2

total = i* V1 + j* V2;

If (total == Sum)
return i V1   j V2;
else
continue;
```

Above is actually the essence of the brute-force approach (described at the end), but your final solution isn't, as you will know soon. You have, in your code, optimized the algorithm above to loop only for (Sum - V2) / V1 and (Sum - V1) / V2, respectively, to reduce looping. This is because when you consider a Sum S with two components V1 and V2, V1 should be repeated so that at least one V2 can be added to form S, and vice versa for V2. (If it is not clear, try putting 5 and 25 for V1 and V2, for S = 100).

Do not forget that you are attempting combinations of exactly two coins that form a sum—a combination of a single type of coin is separately arrived at, and isn't really a rocket science thing. A hundred can be formed using 100 1s, 2 50s, 4 25s, or 20 5s, and even a child can tell you that this can be done by simple division. That's why you have taken two numbers as the building block of your algorithm, and not one.

The corrected, optimized, algorithm now is:

```For i = 1 to (Sum - V2 ) / V1
For j = 1 to (Sum - V1 ) / V2

total = i* V1 + j* V2;

If (total == Sum)
return i V1  j V2;
else
continue;
```

You have accomplished the first step: obtaining all combinations of two coins that form a sum S. In code, the Comb2() function corresponds to this functionality, which takes two int parameters a and b, and yields all combinations of them that total up to sum S. As a return value, I have chosen the type vector<map <int> >, because you expect a number of combinations, each having two (or more) coin values (keys of map) V1 and V2, and their respective required numbers (values of the map).

A partial output of the Comb2() function with coin values a=5, b=25 to obtain sum = 100:

```Output Vector Vect: contains Vect1, Vect2....VectN

Vect1: 5 : 5  25 : 3 --- 5 coins of 5 cents, 3 coins of 25 cents.

Vect2: 5 : 10  25 : 2 --- 10 coins of 5 cents, 2 coins of 25 cents.
```
Note: The order in actual output may differ; this is only for illustration. Also, this only shows two elements of the resultant vector.

Now, look at the three-coin combinations that total 100; all three are required in every combination. Take as an example 1 cent, 5 cent, and 25 cent coins to form a dollar. You already have a method to obtain any sum from coins 1 and 5. The other coin remaining is 25. Your target sum is 100.

So, change your target sum to 100 - 25 = 75. Try obtaining combinations of 1 and 5 for sum 75. Comb2() will give you the vector of vectors. Once you have it, append exactly one 25 to every combination, and you have a 100!

Next, change your target sum to 100 - 2*25 = 50. Try obtaining combinations of 1 and 5 for sum 50. Comb2() will again give you a vector of vectors. Once you have it, append exactly two 25s to every combination, and again you have a 100!

There is room for one more 25. So, repeat the process above by multiplying 25 by 3, try to obtain combinations for sum 25, and you are done with this one.

Just as you excluded 25 above, you just need to repeat this process, once for 5, and once 1, to arrive at all the combinations.

After you have all the combinations, you can repeat the above process taking 5, 25 and 50; 25, 50, 1; and 50, 1, 5.

This is what exactly the Comb3() function does. It takes three int parameters—a, b, and c—and yields all combinations of them that total up to sum S. As with Comb2(), it again returns vector of maps, with keys as coin values V1, V2, V3... and values as their required number a, b, c....

This can propagate to more levels. Comb4() takes it to the sum of four different coin values, with the buildup already done by Comb3(), and so on. This can be generalized to use recursion (just like factorials), but for the puzzle's sake, I have limited myself to four coin combinations.

Finally, take a look at the Brute Force approach, which is infinitely extensible to contain any number of coins, but incurs high processor activity and memory usage due to excessive looping.

### The Brute Force Approach

This takes all coins, one at a time, and puts them into nested For loops to arrive at combinations that form the given sum:

```For i = 1 to Sum / V1
For j = 1 to Sum / V2
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
For r = 1 to Sum / VN

total = i* V1 + j* V2;

If (total == Sum)
return i V1   j V2 ... r VN;
else
continue;
```

As you can see, it tries to match everything with everything, and no optimizations are performed.

As a means of comparison to the DP approach, I have included a BruteForceTest() function in the code; it also will take three parameters corresponding to three coin values, and yield combinations that total up to a desired sum S.

The .exe is a console application that displays all combinations with both the approaches. Conditionally, one also can log the results to a file by uncommenting a #define DO_LOG line. The code displays the time taken by both the approaches, and also logs them if logging is enabled. The logging for both approaches happens to two different files for easy comparison.

In my test runs, BruteForceTest() takes around 15+ ms on a Windows XP workstation as well as a Windows 2003 Server. The DP approach completes in almost 0 ms. Repetitive runs reduce the BruteForceTest() running time to 0 ms, but this is due to binary code being cached. With a higher number of coins, the DP approach can definitely add substantial performance gains.

I would like to hear from all because this is my first CodeGuru submission. Your comments and suggestions are welcome for the article as well as the code.

#### Nirav Bhatt

A VC++ vetaran. Currently Working in GUI team of a world class Enterprise Product company's India office.

• #### Shubham

Posted by Shubham on 04/29/2015 07:03am

Excellent work... I understood DP approach actually.. Thank you for your efforts.. Keep it up.

• #### uno de los estilos GHD estÃ¡n en descuento

Posted by swvlcy317 on 07/17/2013 11:06pm

• #### kÃ¸be billige sort GHD glattejern,nye ghd IV sort

Posted by carpinteyrohvg on 06/14/2013 11:34pm

[url=http://ghdfladjerntilbud.webstarts.com/]GHD fladjern tilbud[/url] GHD Limited LyserÃ¸d er altid viser en stor stigning tendens til i denne sÃ¦son pink er en af tendensen i denne sÃ¦son. Den er udstyret med avancerede funktioner, sÃ¥som forbedret temperaturkontrol at bevare varme under styling, en dvaletilstand, og universelle spÃ¦nding. Hertil kommer, GHD den perfekte styling af New Smukke Pink Styler Box sÃ¦t er en hemmelighed, forÃ¥rsager alt er indkapslet i en smuk Ã¦ske, hvilket gÃ¸r dette sÃ¦t en perfekt gave!Du kan nyde gratis forsendelse til Danmark, ingen skat og spare op 50% off. Hvis du har andre spÃ¸rgsmÃ¥l, sÃ¥ kontakt os. vi har evnen til at levere dig den bedste service. TÃ¸v ikke med, gribe chancen for at kÃ¸be mode ghd fladjern.ghd glattejern er det absolut ypperste indenfor hÃ¥rstyling. Med et ghd glattejern, kan du nemlig ikke bare glatte dit hÃ¥r â du kan ogsÃ¥ bruge dit ghd glattejern til at skabe store, voluminÃ¸se glamourkrÃ¸ller, bevÃ¦gelse i lÃ¦ngderne, svej i nakken eller masser af volume pÃ¥ toppen. [url=http://glattejernghd.bloguedobebe.com/]Glattejern ghd[/url] Ligesom enhver anden hÃ¥rudglatningsmiddel i ghd hÃ¥r stabil, den metalliske Collection glattejern garanteret sikker at bruge. De er drevet ved hjÃ¦lp universel spÃ¦nding, hvilket gÃ¸r dem praktisk for styling farten. De metalliske serien stylers ogsÃ¥ komme med en varme-bevis sag og en to-Ã¥rig garantiperiode.Den Metallic Collection indeholder tre ghd glattejern med et slankt og skinnende finish. De er nemlig: ghd skinnende Silver Metallic Series Styler, ghd Rich Ruby Red Metallic Series Styler, og ghd Sahara Gold Metallic Series Styler.Hver ghd glattejern i Metallic Collection har de samme innovative funktioner som den klassiske ghd guld V glattejern, en af de bedst sÃ¦lgende stylers i ghd produktlinje. Disse stylers er velegnede til alle hÃ¥rtyper. OgsÃ¥ med deres keramisk varmelegeme teknologi designet til at forsegle fugt i individuelle hÃ¥r trÃ¥de, er disse stylers alle garanteret til at give ekstra glans og glans til hÃ¥ret, hvad enten det er krÃ¸llet, vinkede eller stryges lige. [url=http://glattejernghdpris.webgarden.es/]Glattejern ghd pris[/url] Nu er jeg overvejer at kÃ¸be en, fordi selvom jeg BABYLISS er fair, sÃ¥ vil jeg gÃ¸re mig fÃ¸le sig afslappet, ikke spilde for meget tid og bÃ¸lge hÃ¥r, jeg Ã¸nsker at kÃ¸be guld klassiker, dette er mit hÃ¥r barber shop, i Her kan du finde, hvis du vil have en begrÃ¦nset udgave af kassen er omkring 199 â¬, men de er online, kan du finde ganske billige â¦ BemÃ¦rk dog vÃ¦re forsigtig, fordi der er en masse af efterligning, kan du sÃ¦lge en Den falske priser vÃ¦ksthormonmangel.

• #### Optimized brute force method

Posted by bkirunge on 07/21/2009 05:58am

Below code will significantly reduce number of iterations in BruteForceMethod.

for (w=0; w<=S/d; w++) {
for (x=0; x<=(S-w*d)/c; x++) {
for (y=0; y<=(S-(w*d+x*c))/b; y++) {
for (z=0; z<=(S-(w*d+x*c+y*b))/a; z++) {
int val= w*d + x*c + y*b + z*a;
if (val == 100) {
map temp;
temp[a] = z;
temp[b] = y;
temp[c] = x;
temp[d] = w;
retVect.push_back(temp);
}
}
}
}
}

• #### recursive version

Posted by mendi80 on 02/05/2009 07:23pm

```#include
#include

int ways_num(int,int[],int);

void main()
{
int Nums[]={1,5,20};
int sum=20;
int size=sizeof(Nums)/sizeof(int);
int numofways = ways_num(sum,Nums,size); //algorithm
printf("N=%d\n", numofways);
getchar();
}

int ways_num(int s, int arr[],int arrsize)
{
if (s<0)
return 0;
else if	(s==0 || arrsize==1)
return 1;
else
return ways_num(s,arr,arrsize-1)+ways_num(s-arr[arrsize-1],arr,arrsize);
}```

• You must have javascript enabled in order to post comments.

## Top White Papers and Webcasts

• Lenovo recommends Windows 8 Pro. "I dropped my laptop getting out of the taxi." This probably sounds familiar to most IT professionals. If your employees are traveling, you know their devices are in for a rough go. Whether it's a trip to the conference room or a convention out of town, any time equipment leaves a user's desk it is at risk of being put into harm's way. Stay connected at all times, whether at the office or on the go, with agile, durable, and flexible devices like the Lenovo® …

• On-demand Event Event Date: September 23, 2015 The cloud is not just about a runtime platform for your projects – now, you can do your development in the cloud, too. Check out this webcast to learn how the cloud improves your development experience and team collaboration. Join Dana Singleterry, Principal Product Manager for Oracle Dev Tools, as he discusses how to simplify every aspect of the development lifecycle, including requirements gathering, version management, code reviews, build automation, and …