蓝桥杯之平方拆分_c++蓝桥杯 平方拆分

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

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

题解：一看就是DFS，但是难点就是怎么两两不同和无序性。

这个题和整数分解为若干项之和有异曲同工之妙，要在函数中设置一个begin，循环的时候就可以避免重复和保证无序性。

ACCODE：

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
int a[50]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936};
vector<int>v;
int ans;
int sum;
void dfs(int begin) //begin！！！！
{
	if(sum==2019){
		ans++;
		return;
	}
	else if(sum>2019)return;
	for(int i=begin;i<=44;i++){// i=begin  很重要，同时保证 1、两两不同 2、无序性
		sum+=a[i];
		dfs(i+1);//这个题是i+1，不能重复，那个题能重复是传的i;
		sum-=a[i];
	}
}
int main()
{
	dfs(1);
	cout<<ans<<endl;
	
}