8个互不相同三位正整数之和是1234四个数字组成的四位数,这样的组合有多少个?

8个互不相同三位正整数之和是1234四个数字组成的四位数,这样的组合有多少个?

例如:
100+200+300+324+400+500+600+700=3124。

八个数之和为1234,或1243,或1324……4321等24种情形的,都计算在内。

求:算法;代码;运行结果;时耗。

100+200+300+324+400+500+600+700=3124

先确定个问题,以下两种情况不在目标组合里吧?
100+100+400+324+400+500+600+700=3124。
100+400+100+324+400+500+600+700=3124。

能想到比较简单的思路是,分配8个100 到列表里,然后用目标数3124-800=2324 , 做8层遍历, 依次加到列表中的8个数里,新数如果在结果集中出现,忽略。

这样,问题就转换为 求8个不重复整数,和为2324的问题。
递归算法,把 0-2324 数用完,取8个数,如果和为2324 ,输出。

找到了答案,不是用枚举算法。枚举太耗时了。

img