algorithm - 将自然数表示为不同平方和

Question

问题是找到最大的正整数集合S，使得S的元素的平方和等于给定数n。

例如:

4 = 2²
20 = 4² + 2²
38 = 5² + 3² + 2²
300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1².

我有一个运行时间 O(2^(sqrt n) * n) 的算法，但它太慢了(正方形的每个子集)。

Answer 1

有一个 O(n^1.5) 时间算法基于 subset sum 的规范动态程序.这是重复的:

C(m, k) is the size of the largest subset of 1..k whose squares sum to m
C(m, k), m < 0 = -infinity (infeasible)
C(0, k) = 0
C(m, 0), m > 0 = -infinity (infeasible)
C(m, k), m > 0, k > 0 = max(C(m, k-1), C(m - k^2, k-1) + 1)

为 0..n 中的所有 m 和所有 k 计算 C(m, k) 0..floor(n^0.5)。为目标值返回 C(n, floor(n^0.5))。要恢复集合，请追溯 argmax。