一个组合数的递归问题

Question

设定输入N个数 a1,a2,a3...an和一个总和 sum
列出所有可能由开始输入的N个数任意组合求和为sum的可能。
如 输入1,2,5 ，设定sum=10  则列出下面情况 
5*2=10
5+2*2+1*1=10
5+2+1*3=10
2*5=10
2*4+1*2=10
2*3+1*4=10
2*2+1*6=10
2*1+1*8=10
1*10=10

Answer 1

这个问题没法用递归做，因为数和SUM都不定，而且还是组合运算，不大可能又算法能搞出来

Answer 2

如 输入1,2,5 ，设定sum=10  则列出下面情况 ===========
下面的3,4,6,8,10等是怎么回事?
这个貌似是4张扑克算24的问题，比较复杂

Answer 3

楼上的兄弟们  别乱说话  没见楼主只用了+号么？人家又没用减号 你们别误导人家啊是有解的举个例子 比如1 2 5 SUM=13这个先找出最大数5 找不大于10的5的最大倍数倍数10
然后再找第二大的数的最大倍数相加 也就是2*1（乘号是指+两次，实际只能使用+号）
这时是5*2+2*1 然后取下一个大的数也就是1*1
然后5变成*1 继续取思路就是这样这个算法可以使用递归假设解答为F（sum,a1,a2,...,an)
则递归为F(sum,a1..an)=F(sum-an,a1,...an-1)+F(sum-an*2,a1,..an-1)+...代码就自己去写吧

Answer 4

哥们,这样递归写不下去
F(sum,a1..an)=F(sum-an,a1,...an-1)+F(sum-an*2,a1,..an-1)+...
a1的乘数可以从0-sum/a1
a2的乘数可以从0-sum/a2
...
an的乘数可以从0-sum/an
整个问题的难点就在这里,因为n的不确定,我就在这不知道如何实现了 

Answer 5

什么叫N的不确定？
SUM和an数列当然要是给定的了比如你自己的例子 sum=10 {an}={1，2，5}

Answer 6

如果SUM比较小还好，大了的话，这个计算就海了。
假设SUM=1000000,AN={1,2}，那就是500000种可能
如果AN={1,2,3}
如果AN={1,2,3,100}

Answer 7

是,在每次运行时N可以确定,但你的循环如何做?
你如何去实现an后面乘的那个数循环,整个算法要处理的难点就在这

Answer 8

for(int i=0;an*i<sum;i++)
{
}