算是一道算法题

Question

碰到这样一个问题。给定一组数组作为基数，然后给一个数字，求出所有以数组值为基数的数量和为给出数字值的组合。

举例简单说明吧：假定一个简单的数组arr[3]={2,3,6}，然后

给出数字8的组合有三种：(2->4); (6->1)(2->1); (3->2)(2->1)

给出数字9的组合也有三种：(3->3); (6->1)(3->1); (2->3)(3->1)

PS：本人用C#写了个三重循环加递归，感觉有点复杂了，希望有高手帮忙分析下有没有什么简单的算法或者数据结构的解决思路。题目本身也不算难吧，但自己实际写写也花了点时间，所以想提出问题，请各位高手帮忙分析分析，谢谢。

除了蛮力遍历没有什么高端的算法么？

Answer 1

可不可以这样子一下，你有一个基数数组，一个给定的数字。可以确定一个最大可能的基数的系数，也就是给定的数字除以基数数组里的每一个数，得到的最大的那个数就是可能的最大的系数。然后你可以造一个（最大系数+1）进制类，这个仿照10进制建个类应该可以做到然后进行一次遍历，范围是从0到（最大系数+1）进制的数组长度位的最大值然后对数组的第1，2。。。个元素分别乘以循环的数的第1，2。。。位上的数，查看相加的结果是不是等于给定的数字，等于的话则说明这组数字是可用的。这样建一个类，一次循环就可以了。