2019\National _C_C++_C\試題 C: 平方拆分

【問題描述】
將 2019 拆分為若干個兩兩不同的完全平方數之和，一共有多少種不同的方法？

注意交換順序視為同一種方法，例如 13² + 25² + 35² = 2019 與 13² + 35² + 25² = 2019 視為同一種方法。

【答案提交】

這是一道結果填空的題，你只需要算出結果後提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多餘的內容將無法得分。

DFS

直接打暴力有點慢，Python大概跑了兩三分鐘，但無所謂，填空題嘛，能暴力出來就懶得動腦子了。

Python

def dfs(num, minn, maxn):
    if num < 0:
        return
    if num == 0:
        global ans
        ans += 1
        return
    for i in range(minn, maxn + 1):
        dfs(num - i ** 2, i + 1, maxn)

ans = 0
dfs(num=2019, minn=1, maxn=45)
print(ans)

Answer：26287

如果完全平方數包括0的話，結果需要乘2，也就是52574。