ruby - 幂和递归算法

Question

我正在研究一种算法，其中我们有两个输入、一个总量和一个功率值。我们必须找到总和为总数的幂参数的唯一数字组合的总数。

例如:给定 amount = 10 和 power = 2，只有一个唯一的解决方案:(1^2) + (3^2) = 10

(问题出自这里:https://www.hackerrank.com/challenges/the-power-sum)

到目前为止，这是我的算法:

def count_unique_combos(total, candidate, power)
  return -1 if total < 0 || candidate > total # this means impossible to continue
  return 1 if total == 0 # arrived at our goal
  num_ways = 0

  # all the ways to get the total amount, if we use candidate ** power
  with_candidate = count_unique_combos(total - candidate ** power, candidate + 1, power)
  num_ways += with_candidate if with_candidate != -1


  # all the ways to get the total amount without using the candidate.
  without_candidate = count_unique_combos(total, candidate + 1, power)
  num_ways += without_candidate if without_candidate != -1

  num_ways
end

这就是我感到困惑的地方。我已经阅读了很多关于递归算法的信仰飞跃的文章，其中您假设您具有适用于 N-1 输入的函数，并且您只需要使其适用于输入大小 N 并放入正确的基本情况。

基本情况对我来说似乎是合理的，递归关系也是如此(获取所有具有此数字的唯一组合，获取所有没有此数字的组合)。

但是，我的输出不正确。对于 amount = 10 和 power = 2，我的结果值为零。有谁知道我在哪里不符合逻辑？

Answer 1

尝试交换基本案例

  return 1 if total == 0 # arrived at our goal
  return -1 if total < 0 || candidate > total # this means impossible to continue

当 total == 0 时，您传入的任何候选人(因为您只会增加候选人)将成为 candidate > total 并且您将以-1，然后再检查您是否达到了积极的基本情况。

当你交换它们时(使用 tadman 的测试用例，以便于比较)

count_unique_combos(10, 1, 2)
# => 1
count_unique_combos(100, 1, 2)
# => 3
count_unique_combos(100, 1, 3)
# => 1