将JavaScript实现的动态规划howSum函数转换为C++代码的咨询

实现思路 #

• 对应JS中可以返回数组或null的特性，C++使用std::optional<std::vector<int>>作为返回类型：存在可行解时返回存储了数字组合的std::vector<int>，无可行解时返回std::nullopt对应原逻辑的null，目标和为0时返回空std::vector<int>完全匹配原逻辑。
• 不需要使用C风格的数组指针和realloc，std::vector会自动管理内存，插入元素直接调用push_back或用初始化列表拼接即可，和JS的展开运算符逻辑等价。
• memo参数不建议用静态默认值（会导致多次调用函数时缓存残留），你现在用函数重载的方式实现对外隐藏memo参数的效果是最优方案。

完整实现代码 #

#include <vector>
#include <unordered_map>
#include <optional>

// 内部递归实现，接收memo引用
std::optional<std::vector<int>> howSum(int targetSum, const std::vector<int>& numbers, std::unordered_map<int, std::optional<std::vector<int>>>& memo) {
    // 命中缓存直接返回
    if (memo.count(targetSum)) {
        return memo[targetSum];
    }
    // 基础条件
    if (targetSum == 0) {
        return std::vector<int>{};
    }
    if (targetSum < 0) {
        return std::nullopt;
    }

    for (int num : numbers) {
        auto res = howSum(targetSum - num, numbers, memo);
        if (res.has_value()) {
            // 拼接当前数字，存入缓存
            res->push_back(num);
            memo[targetSum] = res;
            return res;
        }
    }

    // 无可行解，存入缓存
    memo[targetSum] = std::nullopt;
    return std::nullopt;
}

// 对外暴露的接口，自动创建memo
std::optional<std::vector<int>> howSum(int targetSum, const std::vector<int>& numbers) {
    std::unordered_map<int, std::optional<std::vector<int>>> memo;
    return howSum(targetSum, numbers, memo);
}

兼容低版本C++的替代方案 #

如果你的编译环境不支持C++17的std::optional，可以改用std::pair<bool, std::vector<int>>作为返回类型：第一个元素为true表示存在可行解，第二个元素存储组合；第一个元素为false对应原逻辑的null。

使用示例 #

#include <iostream>

int main() {
    auto res = howSum(7, {2, 3});
    if (res.has_value()) {
        for (int n : res.value()) {
            std::cout << n << " ";
        }
        // 输出 3 2 （顺序和JS实现一致，为递归回溯时拼接的数字）
    } else {
        std::cout << "无可行解";
    }
    return 0;
}

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