记忆化BestSum函数Lua转写结果错误问题排查

你的Lua代码存在两个核心错误，本质是JavaScript和Lua的表/数组传递逻辑差异导致的：

• 引用传递未做拷贝：Lua中表是引用类型，你写local combination = remainder_combination并没有生成新数组，只是把变量指向了记忆化缓存里已有的数组。后续执行table.insert(combination, num)会直接修改memo中存储的缓存结果，导致缓存被持续污染，返回的数组长度、内容完全失真。而原JS代码中[...remainderCombination, num]会通过扩展运算符生成新的浅拷贝数组，不会修改原有的remainderCombination。
• 缺少memo参数默认值：原JS代码给memo设置了默认空对象，你的Lua代码没有做默认值初始化，调用时如果漏传memo参数会直接报错。

首先需要实现一个数组浅拷贝的工具函数，每次生成新组合前先复制递归返回的缓存数组，避免直接修改缓存：

-- 数组浅拷贝工具函数
local function copy_array(arr)
    local new_arr = {}
    for _, v in ipairs(arr) do
        table.insert(new_arr, v)
    end
    return new_arr
end

local function BestSum(target_sum, numbers, memo)
    -- 初始化memo默认值
    memo = memo or {}
    if memo[target_sum] ~= nil then
        return memo[target_sum]
    end
    if target_sum == 0 then
        return {}
    end
    if target_sum < 0 then
        return nil
    end

    local shortest_combination = nil

    for _, num in ipairs(numbers) do
        local remainder = target_sum - num
        local remainder_combination = BestSum(remainder, numbers, memo)
        if remainder_combination ~= nil then
            -- 先复制数组，再追加当前num，避免修改缓存
            local combination = copy_array(remainder_combination)
            table.insert(combination, num)
            if shortest_combination == nil or #combination < #shortest_combination then
                shortest_combination = combination
            end
        end
    end

    memo[target_sum] = shortest_combination
    return shortest_combination
end

执行以下测试用例可以得到符合预期的结果：

-- 测试用例
print(table.concat(BestSum(7, {5,3,4,7}, {}), ","))    -- 输出：7
print(table.concat(BestSum(8, {2,3,5}, {}), ","))      -- 输出：3,5（或5,3，均为长度2的最短组合）
print(table.concat(BestSum(8, {1,4,5}, {}), ","))      -- 输出：4,4
print(table.concat(BestSum(100, {1,2,5,25}, {}), ",")) -- 输出：25,25,25,25
print(table.concat(BestSum(150, {5,25}, {}), ","))     -- 输出：25,25,25,25,25,25（总长度6的最短组合）

在Lua中实现记忆化递归时，只要需要修改递归返回的表类型结果，必须先做拷贝，绝对不能直接修改引用指向的缓存内容，否则会导致缓存污染，所有依赖该缓存的后续计算都会返回错误结果。

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