平方拆分-蓝桥杯国赛java_平方和拆分蓝桥杯

平方拆分：
本题总分：5 分
【问题描述】
将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方
法？
注意交换顺序视为同一种方法，例如 13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +
25 2 = 2019 视为同一种方法。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
分析：
我们只需要使用深搜就行，首先将前几位数数字的平方全部都加入进去，之后如果发现num这时候已经小于零了，就说明现在这种情况不适合，就将刚才加入的数字重新删除，在加入下一个数字进行判断。

package 第十届;

public class 平方拆分{
	public static int sum = 0,max = 45;
	public static void main(String[] args) {
		dfs(2019,1);
		System.out.println(sum);
	}
	public static void  dfs(int num, int min) {
		if (num < 0) {
			return;
		}
		if (num == 0) {
			sum ++;
			return;
		}
		for (int i = min; i < max; i++) {
			dfs(num - i * i, i + 1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

多使用这种方式，尽量少使用先生成全排列之后在去找中间的情况。