我怎样才能让这个算法更有效地解决一个难题？

Question

谜题是：给定一个数字 n，我需要 return 一个包含所有平方和等于 n^2 的数字的数组，按递增顺序排列。例如：[3,4] 是一个有效的解决方案，因为 3^2 + 4^2 = 25，但对于 n = 50，[1, 1, 4, 49] 不会，因为 1, 1 不是递增序列。该测试还提到，如果两个或多个序列有效，我们应该选择最终数字最大的一个。如果没有找到解决方案，它应该 return None。然后，我编写了这段代码，它成功地通过了 n 是 5 和 8 的两个初步测试，但在更大的测试中超时，这是可以预见的。那么，我怎样才能让它更有效率呢？我正在考虑使用生成器，但无法决定在哪里：

def decompose(n):
    add = []
    result = []
    for i in range (n-1, 0, -1):
        if sum(add) < n ** 2:
            add.append(i**2)
            result.append(i)
        elif sum(add) > n ** 2:
            add.pop()
            result.pop()
        elif sum(add) == n ** 2:
            return sorted(result)
    return None

Answer 1

这没有针对速度进行优化，但它确实提供了正确的解决方案。诀窍是使用递归。这个问题的关键变量不仅是 n 本身，而且是列表中的元素必须具有的总和。最初这是 n**2，但每次添加新元素时，剩余的总和都会降低，之后可以添加到列表中的最大整数也会降低。因此，向列表中添加一个新数字又是老问题，但有不同的约束。这使得这是一个递归问题，也是何时使用 yield 和 yield from.

的绝妙示例

def decompose(max_n, sum_allowed, solution):
    for x in range(max_n, 0, -1):
        left_over_sum = sum_allowed - x**2
        if left_over_sum == 0:
            yield [x] + solution
        elif left_over_sum > 0:
            yield from decompose(x-1, left_over_sum, [x] + solution)
    yield None

def decompose_top(n):
    generator = decompose(n-1, n**2, [])
    return next(generator)

print(decompose_top(1000001))

在这台有 7 年历史的机器上，我只需一秒钟的执行时间就可以轻松地达到 n=100000。通过多次调用生成器上的 next()，可以看到给定 n 的所有可能的解决方案。

我怎样才能让这个算法更有效地解决一个难题？

How can I make this algorithm more efficient for a puzzle?

python

puzzle

timeout