如何解决递归回溯问题

Question

我有一个学校的递归回溯问题，我不明白我将如何解决它。

给定一个整数数组，确定是否可以从这些整数中选择一组来增加特定的总和。使用称为 sum_to_total 的递归方法来解决问题（没有循环！）。

示例：

"Array [3, 6, 7]" 和 "Sum 10" returns 正确，因为 3 + 7 = 10
"Array [1, 2, 3]" 和 "Sum 6" returns 正确，因为 1 + 2 + 3 = 6
"Array [2, 4, 6]" 和 "sum 5" returns 错误，因为这些数字的组合总和不等于 5

这是我目前得到的：

def self.sum_to_total(sum, array, index)

  @@sum_num += array[index]
  return false if @@sum_num > sum || @@sum_num < sum
  return false if index<board.length || index<0
  return true if @@sum_num == sum

  return solvable(sum, array, index+1) 
end


@@sum_num = 0
puts sum_to_total(10, [3, 5, 7], 0)

一些建议会有所帮助。

Answer 1

您已经尝试过了，所以这里有一些建议可以帮助您继续前进。

"recursive" 是指一个调用自身的方法。您的 solvable 需要拨打 sum_to_total.
如果您必须在下一次调用时访问更新的值，则递归方法需要传入在方法期间更改的任何值。因此，index 是正确的，但您还必须传入 sum_num.
您可以在第一次调用时使用默认值来初始化 index 和 sum_num。您不需要弄乱全局变量。（而且不应该。全局变量是邪恶的。大多数时候。）
您只需要 return 遍历整个数组即可。您不在递归方法调用中使用 return，您只需调用该方法即可。
您无需使用 self.method_name.

我将向您展示基本的递归方法，并让您解决（更困难的）回溯要求。（这个基本方法将解决整个数组是否相加的情况。回溯部分是判断数组的一个子集是否相加所必需的。）

def sum_to_total(sum, array, index = 0, sum_num = 0)
  sum_num += array[index]
  return sum_num == sum if index == array.size - 1
  sum_to_total(sum, array, index + 1, sum_num)
end

三行代码是这样做的：

将当前数组值加到总和中。（你几乎可以接受这个。）
如果您完成了数组的遍历，return数组的总和是否等于提供的总和值。
（如果您还没有完成遍历数组）再次调用该方法，传入递增的索引值和到目前为止的累计和值。（你走对了！）

Here's 一篇对回溯部分应该有帮助的文章。

如何解决递归回溯问题

How to solve a recursive Backtracking problem

ruby

recursion

recursive-backtracking