|
Write a function that takes an array of five integers .....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Write a function that takes an array of five integers .....
Question:
. Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated. Show how you would test this function.
maybe an answer:
Let f[i][j] be the number of combinations of the FIRST I numbers suming up to J.
f[i][j]
=
f[i-1][j-a[i]] //a[i] is selected. of course only if j>>=a[i]
+
f[i-1][j] //a[i] isn't selected
The basic case is f[0][0]=1
The final answer is f[5][15].
int input[5] = {5,5,10,3,2};
int comb(int sum, int cnt)
{
if (cnt == 0 && sum)
return 0;
else if(sum == 0)
return 1;
int i,n;
int tempsum=0;
for (i=cnt-1; i>=0; i--)
{
tempsum += comb(sum - input[i], i);
}
return tempsum;
}
(Continued on next question...)
Other Interview Questions
| 