algorithm - 不同整数的平方和

Question

能否请您提出解决以下问题的任何算法思路:

Given positive integers S, K ≤ N. Find distinct positive integers x₁, x₂, ..., x_K such that

   x₁² + x₂² + ... + x_K² = S

x_i ≤ N and x_i < x_i+1 for all i = 1...K.

到目前为止，我知道我应该开始搜索S 的平方根以下的最大x。

Answer 1

这是一个略微优化的蛮力。正如我在评论(和关闭投票)中所链接的那样，在我看来我们可以修改标准子集和问题以使用正方形。

JavaScript 代码(输出末尾的省略号表示将其余数字加到 1):

function f(S, K, N){
  function g(s, k, n, c){
    const minS = k*(k+1)*(2*k+1)/6;
    const maxN = Math.min(
      n,
      ~~Math.sqrt(s - (k-1)*k*(2*k-1)/6)
    );

    if (s < minS || maxN < 1)
      return [];
    else if (s == minS)
      return [c.concat([k, '...'])];
    if (k == 0)
      return [];
    
    return g(s - maxN*maxN, k - 1, maxN - 1, c.slice().concat(maxN))
      .concat(
        g(s, k, maxN - 1, c)
      );
  }
  
  return g(S, K, N, []);
}

for (let j=1; j<6; j++)
  console.log(JSON.stringify([178, j, f(178, j, 100)]));

console.log(JSON.stringify([178, 5, f(178, 5, 10)]));