Count the number of combinations that add to a given sum in an int array


My roommate Long Tran gave me a coding problem he found on the Internet this afternoon. I first did not think it was actually a coding problem but a puzzle. He gave me 2 samples of integer arrays: 5,5,10,2,3 and 1,2,3,4,5. The goal is finding the number of combinations which add up to 15. I started to break down the problem to picking 1,2,3,4,5 numbers in any combination because combination does not care about order but which element is picked. If you can find the possible combination from picking 1,2,3,4,5 numbers and count how many of them will produce 15 as the sum, you score. Everything seemed to be easy from the given 2 integer arrays. But the real problem comes to arbitrary array and a given sum. What if I want you to code such a program that takes an integer array and a number as sum and produces the count of combinations of picked elements which add up to the given sum?

I started to think if 2 elements are picked, pick the 1st from any element and pick the 2nd from any element after the 1st element would exhaust all combinations of picking 2 elements. The same rule applies to picking n elements. I knew if I focused on solving picking 2 elements and get the count, I’d be half way there. To pick the 1st element, I need a for loop to pick any element. To pick the 2nd element, I need a recursive function (CountSum) that starts from the next element (StartIndex) of the 1st element to the last, which will be the same for loop but the starting index will be 1 ahead. This is only 1/3 of the problem. To solve picking n element instead of 2, the concept of depth (DepthLeft) needs to be introduced. Depth means how many recursions are needed. In the case of picking 2 elements, 2 recursions are needed. Each recursion counts as 1 invocation of the function.

How do I record the sum from the previous recursion? If I pick 2 elements, the 2nd recursion needs to know which element in the previous was added to the sum. The function needs to pass the accumulated sum (AccumulatedSum) from past recursions. At the recursive call, add the chosen element and the previous sum as the (AccumulatedSum) parameter. Remember to set (StartIndex) to the chosen index + 1 and decrement (DepthLeft).

The base case of the recursive function is when (DepthLeft) is 0 meaning there is no more element to pick. In that case, the function must return. Before returning, check if (AccumulatedSum) is equal to the given sum. If yes, increment the counter. Now, you have the recursive function complete. In the main function, iterate through the array on (DepthLeft) from 1 to the array’s length with (StartIndex) and (AccumulatedSum) set to 0. The attached Visual Studio 2010 solution takes “InputArrayFile” and generates “OutputResumeFile” with the count.

Another side question is how do you record the combinations which add to the given sum? If I say, not only give the count but tell me those combinations that add up to the given sum. Can you improve the code to do that?

ArrayCountSum.zip

Comments (2)
  1. bimmerone says:

    can i get all the combination of 1-49

  2. cherry says:

    British reporters are known for doing almost anything to get a Mulberry Bags. But reports that a newspaper secretly listened to telephone messages of murdered schoolgirls and other private citizens have produced Mulberry Handbags and anger.

    On Friday, British police arrested Andy Coulson, former editor of Mulberry Bag Britain's best-selling newspaper, News of Mulberry Outlet the World. The investigation led him to Mulberry UK Sale resign in January as communications director to Prime Minister David Cameron.

    The arrest came in a widening investigation of Mulberry UK telephone hacking. Other accusations include paying police for mulberry shoulder bags information on stories. The Reuters news agency reported that Mr. Coulson was released on Mulberry Bag UK until a date in October.

    Prime Minister Cameron promised Men's Mulberry Bags Friday that a judge will lead a full public inquiry into Women's Mulberry Bags the case after police complete their investigation.

    DAVID CAMERON: "Murder victims, terrorist victims, families who have lost loved ones, sometimes defending our country, that these people could have had their phones hacked into, in order to generate stories for Mulberry Bags  Mulberry Handbags  Mulberry Bag   Mulberry Outlet  Mulberry UK  mulberry bayswater bag  Mulberry Alexa Bag, is simply disgusting."

Comments are closed.

Skip to main content