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?