Represent natural number as sum of distinct squares

Question

The problem is to find the largest set S of positive integers such that the sum of the squares of the elements of S is equal to a given number n.

For example:

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

I have an algorithm that runs in time O(2^(sqrt n) * n), but it's too slow (every subset of squares).

Answer 1

There's an O(n^1.5)-time algorithm based on the canonical dynamic program for subset sum. Here's the recurrence:

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)

Compute C(m, k) for all m in 0..n and all k in 0..floor(n^0.5). Return C(n, floor(n^0.5)) for the objective value. To recover the set, trace back the argmaxes.

Answer 2

I was just wondering if this problem reduce to NP? Looks like you have list of integers (squares) less than n (could be generated in O(sqrt(n))) and you're looking for subset sum of size from 1 to sqrt(n) (check all posibilities). If so it should be solvable with knapsack dynamic programming algorithm (but this is pretty naive algorithm and I think it could be improved) in O(n^2) - sqrt(n) of problems to check times sqrt(n) knapsack items count times n knapsack weight.

EDIT: I think with smart backtracking after filling dynamic programming array you could do it in O(n*sqrt(n)).