如何判断正整数可被表示为n个互不相同正整数的平方和

我已经掌握了通过暴力法判断一个数能否表示为两个平方数之和的方法，现有实现代码如下：

def sumSquare( n) :
    i = 1
    while i * i <= n :
        j = 1
        while(j * j <= n) :
            if (i * i + j * j == n) :
                print(i, "^2 + ", j , "^2" )
                return True
            j = j + 1
        i = i + 1

    return False

我现在需要实现的是判断目标数能否表示为n个互不相同的正整数的平方和，具体需求如下：

实现一个校验函数，判断输入数值是否可以被拆分为n个不同正整数的平方和
两个验证示例：

• is_sum_of_squares(18, 2) 应当返回False，因为18虽然可写为3²+3²，但两个数并非互不相同
• is_sum_of_squares(38,3) 应当返回True，因为5²+3²+2²=38，且三个数互不相等
  我没办法直接扩展现有代码的判断条件来适配任意n的场景，想到可以用递归实现但找不到正确思路。另外我找到了可以求一个数最少可拆分为多少个平方数之和的动态规划代码如下：

def findMinSquares(n):
    T = [0] * (n + 1)
    for i in range(n + 1):
        T[i] = i
        j = 1
        while j * j <= i:
            T[i] = min(T[i], 1 + T[i - j * j])
            j += 1

    return T[n]

我还是不知道怎么基于递归实现符合要求的功能，我是刚接触递归几周的高中生，还不太能适应递归和迭代写法的差异，求对应的实现方法和思路讲解。

递归思路 #

递归的核心是把大问题拆成规模更小的同类型子问题，针对你的需求，拆解逻辑非常直观：
如果要凑出k个互不相同的正整数的平方和等于目标值target，我们可以按从小到大的顺序选数，先选第一个数x，选完之后问题就变成：用k-1个比x大的正整数（自动保证所有数不重复）的平方和凑出target - x²。

边界条件&剪枝逻辑 #

• 当k==0时，只有剩余目标值恰好为0才满足要求，返回True，否则返回False
• 当剩余目标值小于0时，肯定凑不出来，返回False
• 提前计算k个最小不同正整数的平方和：1²+2²+...+k² = k*(k+1)*(2k+1)/6，如果当前目标值比这个最小值还小，直接返回False，不用继续递归

完整实现代码 #

def is_sum_of_squares(target, k, start=1):
    # 边界1：已经凑够k个数，检查剩余目标是否为0
    if k == 0:
        return target == 0
    # 边界2：剩余目标小于0，不可能凑出
    if target < 0:
        return False
    # 剪枝：k个最小不同正整数的平方和都比目标大，直接返回
    min_required = k * (k + 1) * (2 * k + 1) // 6
    if target < min_required:
        return False
    # 从start开始选数，保证比之前选的所有数都大，避免重复
    x = start
    while x * x <= target:
        # 选x之后，剩余k-1个数从x+1开始选，凑target - x*x
        if is_sum_of_squares(target - x*x, k-1, x+1):
            return True
        x += 1
    return False

测试验证 #

直接运行你给的两个示例可以得到正确结果：

print(is_sum_of_squares(18, 2)) # 输出 False
print(is_sum_of_squares(38, 3)) # 输出 True

内容的提问来源于stack exchange，提问作者user1361879