蓝桥杯国赛---平方拆分（dfs）_蓝桥杯第十届决赛真题平方拆分c++

问题描述

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 132 + 252 + 352 = 2019 与 132 + 352 +252 = 2019 视为同一种方法。

思路

暴力dfs，运用递增保证不重复。

#include <iostream>
using namespace std;
typedef long long ll;

ll num=0;

void dfs(int n, int begin)
{
	if (n < 0)return;
	if (n == 0)num++;
	else
	{
		for (int i = begin;i * i <= n;i++)
		{
			dfs(n - i * i, i+1);
		}
	}
}

int main()
{
	dfs(2019, 0);
	cout << num;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25