无法使用递归解决所有情况的幂和

Question

我写了这个问题的代码，但它只适用于 70% 的测试用例。我不知道它有什么问题。请帮忙。

问题：- 找出给定整数 X 可以表示为 [1,25] 范围内的唯一自然数的 N 次幂之和的方式数。

提示：-

答案将是 (1^2 + 3^2)。

我的代码不适用于 x = 100 和 n = 2。输出应该是 3，但它 returns 33。

let x = 100;
let n = 2;
let num = 0;
let index = 1;

function power(x, n, num, index, ways = 0) {
  if (x === num) {
    return 1;
  }
  if (x < num) {
    return 0;
  }
  for (let i = index; i <= 25; i++) {
    ways += power(x, n, (num + ((i) ** n)), index + 1);
  }
  return ways;
}
console.log(power(x, n, num, index));

Answer 1

你的逻辑几乎是对的。但是您没有正确删除重复值并最终包含 9^2 + 3^2 + 3^2 + 1^2 或 5^2 + 5^2 + 5^2 + 4^2 + 3^2.

之类的内容

您需要更改传递的递归索引。您不应使用 index 参数，而应使用循环迭代器 i:

let x = 100;
let n = 2;
let num = 0;
let index = 1;

function power(x, n, num, index, ways = 0) {
  if (x === num) {
    return 1;
  }
  if (x < num) {
    return 0;
  }
  for (let i = index; i <= 25; i++) {
 // ways += power(x, n, (num + ((i) ** n)), index + 1);
 //                                         v-^
    ways += power(x, n, (num + ((i) ** n)), i + 1);
  }
  return ways;
}
console.log(power(x, n, num, index));

我通过从头开始编写自己的函数版本并得到完全相同的错误结果，很快就解决了这个问题。我添加了一些日志记录并意识到了问题并能够快速发现它。这很容易翻译成您的代码。

但我认为我的函数更简洁，所以我将其包含在这里。它的逻辑大致相同，但功能更简洁：

const range = (lo, hi) => 
  Array .from ({length: hi - lo + 1}, (_, i) => i + lo)

const sum = (ns) =>
  ns .reduce ((a, b) => a + b, 0)

const countPowerSums = (n, p, i = 1) =>
  n < 0
    ? 0
  : n == 0
    ? 1
  : sum (range (i, 25) .map (b => countPowerSums (n - b ** p, p, b + 1)))

console .log (countPowerSums (100, 2))

无法使用递归解决所有情况的幂和

Not able to solve the power sum for all cases using recursion

javascript

recursion