排列组合问题

Question

比如：1-100个整数取出 里面个数相加 =50的数字组合如:50,1+49,2+3+45...... 相加的 整数个数不限制。如果上面3个组合正确，再次取 5+45时候就不正确 因为45上次用过了。请问这个算法怎么解决啊？

Answer 1

只能给楼主一些提示。既然和是50，那就把范围限定在1-50就行了。

50=1+49；49=2+47；47=3+44；44=4+40；40=5+35。。。。。

那么在纵向上：50=50；50=1+49；50=1+2+47；50=1+2+3+44；50=1+2+3+4+40。。。。。

横向上：

50=50；

50=1+49；50=2+48；50=3+47.。。。。。2个数那必然是一个大于25，一个小于25

.。。。。。。。。。。。。。。。。。。。。3个数必然必然要有一个数小于16（即50 \ 3）

由于1+。。。+9=45，所以个数不会超过9个，也就是说，在纵向上的范围已经定了。

那么完全可以把纵向上的所有组合写出来，然后从得到横向的所有组合，因为（纵向上使用很多大一部分数，所以横向的集合时很小的），这样就得到了以纵向为基准的组合；在通过同样的方式得到以横向为基准的组合。

Answer 2

这个就是一个多树形问题吧。

比如，首先随便选两个数相加得到50的数，如下：

       50

    25+25

12+13 +13 +12

以此类推。

但是两个数相加得到50的次数一共有多少次？25次吧。