蓝桥杯第十届国赛：2019可拆分的完全平方数方法数

试题 B: 平方拆分

本题总分：5 分

【问题描述】

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方

法？

注意交换顺序视为同一种方法，例如 13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +

25 2 = 2019 视为同一种方法。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

尴尬，感谢大佬的指正，我还以为是只要三位平方数，太马虎了。

题目上要若干个，需要利用深度搜索进行统计。

这里值得注意的是，起始位置应该是从1开始，如果从0开始就会造成下列情况：(用题目的例子举例子)

从0开始深度搜索，会得到 ：( 0 ， 13  ，  25   ， 35) 和(13  ，  25    ， 35)

而从1开始深度搜索，只会得到：(13  ，  25    ， 35)

这两种情况因为没有具体答案，我个人感觉应该第二种，得到的答案：

答案：26287

public class Main {

int sum;

public Main() {

dfs(2019,1,45);

System.out.println(sum);

}

public void dfs(int num, int min, int max) {

if (num < 0) {

return;

}

if (num == 0) {

sum ++;

return;

}

for (int i = min; i < max; i++) {

dfs(num - i * i, i + 1, max);

}

}

public static void main(String[] args) {

new Main();

}

}