python：从1到m这m个数里面取n个不同的数，使它们和是s

多少种取法

描述

给定三个正整数m,n,s问从1到m这m个数里面取n个不同的数，使它们和是s,有多少种取法

输入

多组数据 输入的第一行是整数t，表示有t组数据 此后有t行，每行是一组数据 每组数据就是三个正整数
m,n, s ( n <= 10,s <= 20)

输出

对每组数据，输出答案

样例输入

5
13 4 20
12 5 18
1 1 1
1 2 1
119 3 20

样例输出

22
3
1
0
24

提示：
用函数ways(m,n,s)表示 从1到m这m个数里面取n个不同的数，使它们和是s的取法总数
显然，必须取m个数，不能不取(除非m == 0)

1. 考虑如果 m > s, 问题可以等价于什么？
2. 对于m<= s的情况，把所有的取法分成两类:
   第一类： 取m。则取m后，剩下的问题变成什么？
   第二类： 不取m，那么剩下的问题变成什么？
3. 注意边界条件（即递归终止条件，即不需要递归的条件）
   边界条件一般是 n,m,s = 0, = 1 之类的情况。

例如：
从 1-m这m个数里面，取0个数，使得它们的和是0，有几种取法? 答案是1。
从 1到m这m个数里面，取0个数，使得它们的和是s(s>0)，有几种取法? 答案是0。无解对应的答案就是0.
当 m < n时，答案是0，因为没法取n个数
当 m = 0时，只要m和s有一个不是0，ways(m,n,s)就应该返回0。

递归的时候，函数的参数会减少，如果会出现某个参数一直没完没了减少下去，那就不对了。因此,边界条件一定要考虑周全，确保递归可以终止。

边界条件可以有多种写法。

实现代码：

def ways(m,n,s):
    #第一类，各种特殊情况
    if s<0 or n<0 or m<=0:    #当输入数据小于0时，取法为0
        return 0
    elif n==0 and s==0:     #当n==0且s==0时，只有1种取法
        return 1
    elif n==0 and s>0:     #当取0个，但是s>0时，取法为0
        return 0
    elif n==1:           #判断n=1的情况
        if m>=s:return 1   #若m>=s,只有1种取法
        else :return 0     #若m<s,则取法为0
    elif m>=n and s==0:   #当m>=n 并且 s=0时 ，只有1种取法
        return 1
    elif n>1 and s==1:   #当n>1且s=0时 ，取法为0
        return 0
    
    #第二类，讨论大类
    elif m>s:          #当m>s时
        if n == s or n>s:
            return 0
        elif 1<n<s:
            return ways(s-1,n,s)
    elif m<s:          #当m<s时
        return ways(m-1,n-1,s-m) + ways(m-1,n,s)  #当取m时 与 不取m时 的和
    elif m == s :  #当m=s时
        if n>m:
            return 0
        else:
            return ways(m-1,n,s)
        
t = eval(input())    #  t组数
for i in range(t):
    m,n,s = map(int,input().split())
    print(ways(m,n,s))

总结：

1. 整道题的思路就是用递归，索性它递归的也就是m，n的次数不是很大，所以递归的空间复杂度不是很高，主要也是用来练习递归的。

2. 采用分治的方法，分而治之，大化小。因为这道题特殊情况，也就是m，n，s取0，1时特殊的结果，显得有些复杂，但是把这些情况讨论完，也就只剩第二大类的讨论，只需要考虑数字很小的情况，因为递归调用会使参数逐渐减小，从而使问题简单化。

3. 读题要仔细，是取n个不同的数字，最开始我是写的是可以相同的数字，直接找了4个小时的错误。。

4. 递归调用要有终止条件，其实就是那些特殊情况的讨论。（若你写的题目要求是可以取相同的数字，那只需要改部分特殊情况的返回值即可）

5. 第二大类return的返回值的表达式，只要自己举例就可以了，规律是很明显的。这里举两个例子：
   (1)当m>s时，例如ways（12，3，7），不难发现，7到12的数字是不能取的，相当于ways（6，3，7），以此类推。
   (2)当m<s时，分两种，即取m的和不取的情况，例如ways（7，2，9），取7时等价于ways（6，1，2）即ways（m-1,n-1,s-m）,不取7时等价于ways（6，2，9）即ways（m-1,n,s）

6. 最后说一下map（）内置函数的用法。map() 会根据提供的函数对指定序列做映射。
   map(function, iterable, …)
   第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。
   例如：map(square, [1,2,3,4,5]) # 计算列表各个元素的平方
   还有map(int,input().split()) 把input的字符转化成int类型的数字。