动态规划howSum问题JS转Elixir实现：解决无提前返回终止计算难题

最优原生实现（无额外依赖、纯函数、符合Elixir惯用风格） #

核心用Enum.find_value替代命令式的for循环+提前返回逻辑，Enum.find_value会遍历列表直到拿到第一个非nil/非false的结果就终止，完全匹配需求：

defmodule HowSum do
  @doc """
  从可重复使用的numbers列表中选出元素加和等于target_sum，返回任意符合要求的组合
  """
  def sum(target_sum, numbers) do
    do_sum(target_sum, numbers)
  end

  # 基线条件：和为0返回空列表
  defp do_sum(0, _numbers), do: []
  # 基线条件：和为负返回空
  defp do_sum(target_sum, _numbers) when target_sum < 0, do: nil

  defp do_sum(target_sum, numbers) do
    Enum.find_value(numbers, fn num ->
      remainder = target_sum - num
      case do_sum(remainder, numbers) do
        nil -> nil
        # 把当前数字拼入结果，这里是加在头部，返回顺序和JS示例相反，不影响正确性
        res -> [num | res]
        # 如果要和JS返回顺序完全一致，改成 res ++ [num] 即可
      end
    end)
  end
end

# 测试调用
IO.inspect HowSum.sum(7, [2, 3]) # 输出 [2, 2, 3] 或 [3, 2, 2]（取决于numbers顺序）

带记忆化优化的动态规划版本 #

如果需要处理大数值的target_sum，可以添加缓存避免重复计算，进一步提升性能，纯函数实现无副作用：

defmodule HowSum do
  @doc """
  带DP记忆化优化的版本，适合大数值场景
  """
  def sum(target_sum, numbers) do
    do_sum(target_sum, numbers, %{}) |> elem(0)
  end

  defp do_sum(0, _numbers, memo), do: {[], memo}
  defp do_sum(target_sum, _numbers, memo) when target_sum < 0, do: {nil, memo}
  # 命中缓存直接返回
  defp do_sum(target_sum, _numbers, memo) when is_map_key(memo, target_sum), do: {memo[target_sum], memo}

  defp do_sum(target_sum, numbers, memo) do
    Enum.reduce_while(numbers, {nil, memo}, fn num, {_, current_memo} ->
      remainder = target_sum - num
      case do_sum(remainder, numbers, current_memo) do
        # 没有解，继续遍历下一个数字
        {nil, new_memo} -> {:cont, {nil, new_memo}}
        # 找到解，终止遍历，更新缓存后返回
        {res, new_memo} ->
          result = [num | res]
          updated_memo = Map.put(new_memo, target_sum, result)
          {:halt, {result, updated_memo}}
      end
    end)
  end
end

# 测试大数值也能快速返回
IO.inspect HowSum.sum(300, [7, 14]) # 快速返回 nil

方案优势 #

1. 纯函数实现，无额外进程/状态依赖，没有并发冲突问题，可重入性好
2. 无副作用，逻辑清晰，完全符合Elixir函数式编程的惯用写法
3. 性能优于Agent实现，省去了进程通信、状态读写的额外开销
4. 原生支持提前终止遍历，不需要借助外部状态中断执行

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