蓝桥杯：平方拆分之Python解答_蓝桥杯第十届决赛真题平方拆分c++

B 平方拆分（2019年国赛第二题）
本题总分：5 分

【问题描述】
将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 13^2 + 25^2 + 25^2 = 2019 与 13^2 + 35^2 +25^2 = 2019 视为同一种方法。

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

开始，对这个题目没啥头绪，后来参考了别人的代码，知道要用深搜，我做的工作主要就是将别人的代码翻译成了Python语言，主要参考了 肖有量的博文，大家可以看一下。

import math

L=[]

def dfs(n,start):
    if n<0:
        return
    elif n==0:
        L.append(1)
    else:
        high=int(math.sqrt(n))
        for i in range(start+1,high+1):
            dfs(n-i*i,i)
    
def main(): 
    dfs(2019,-1)
    print(sum(L))

main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里, elif 语句下面本来是用的 cnt+=1，但运行的时候程序报错 local variable ‘cnt’ referenced before assignment ，估计跟递归调用有关，因而我改用在列表L中存1的形式，最后将列表中所有的1加和，即求得所有可能的情况。

此外，dfs(2019,-1)从-1开始，是因为有网友说 0 也是完全平方数，13^2 + 25^2 + 25^2 = 2019 加0的平方与不加0的平方，应算两种情况。