Question

C++输入一个整数m,从1到9中随意抽取几个数(不可重复）,使其和等于m,要求用递归的方法列出所有

发邮箱cgb248@163.com

Answer 1

孩子你不会是南大计算机的吧……

对于一组不大于M的互异的整数集，使之和等于N。
问题分析：

假定M = 1, 则可能的整数集这能为{1}， 所以个数为1。

假定 M= 1，N > 1, 则不可能有合适的整数集，所以个数为0。

假定M > N, 则结果集的个数和M = N的一样多， 因为不可能出现比N大的数。

假定M <= N, M > 1, N > 1, 此时我们有两种情况，结果集中包括M, 或者不包括。最终的数量为这两种情况的数量之和。

假定我们用F(N,M)来表示结果集的数量。则有如下表达式：

F(1,M) = 1; M为任意值.
F(N,1) = 0; N > 1.
F(N,M) = F(N,N); M > N.
F(N,M) = F(N - M,M - 1) + F(N,M - 1);M <= N, M > 1, N > 1.

一般有两种方式来解决这种问题，递归和动态规划。