算法回溯：如何在不存储状态的情况下实现递归？

在回溯算法里，我们通常会借助一个接收初始状态的辅助函数来实现递归逻辑——每一次递归调用都会处理当前的计算任务，再把结果传递给下一轮递归。这个过程我们一般用unseen（待处理的元素集合）和seen（已处理的元素集合）两个变量来直观表示。

拿字符串排列问题举个例子，典型的实现代码会是这样：

def permute(str)
  return str if str.length < 2
  permute_helper(str, "")
end

def permute_helper(unseen, seen)
  # 基准情况：没有待处理元素时，输出已构建好的排列结果
  if unseen.length <= 0
    p seen
    return
  else
    # 遍历所有待处理元素，逐个选择后进入下一层递归
    (0...unseen.length).each do |i|
      # 选择当前元素，更新unseen和seen的状态
      new_unseen = unseen[0...i] + unseen[i+1..-1]
      new_seen = seen + unseen[i]
      permute_helper(new_unseen, new_seen)
    end
  end
end

简单拆解下这段代码的核心逻辑：

• permute是入口函数，当字符串长度小于2时直接返回（单个字符或空字符串的排列就是它本身），否则调用辅助函数permute_helper并传入初始状态：完整的待处理字符串和空的已处理结果。
• 在permute_helper里，首先判断基准情况：如果unseen为空，说明已经构建出一个完整的排列，直接输出seen即可。
• 否则遍历unseen里的每个元素，每次选择一个元素加入seen，同时从unseen中移除这个元素，带着更新后的状态进入下一层递归，完成回溯的核心逻辑。

内容的提问来源于stack exchange，提问作者Saurav Prakash