给定一个目标负载值和一个由2的幂组成的服务器容量数组（如 [1, 2, 4, 8, …]），求最少需选用几个服务器，使其容量之和恰好等于目标负载；若无解则返回 -1。该问题本质是带约束的「最少硬币数」变体，可借助记忆化递归高效求解。

给定一个目标负载值和一个由2的幂组成的服务器容量数组（如 [1, 2, 4, 8, …]），求最少需选用几个服务器，使其容量之和**恰好等于**目标负载；若无解则返回 -1。该问题本质是带约束的「最少硬币数」变体，可借助记忆化递归高效求解。

这是一个经典的最小组合数凑和问题，但具有关键特殊性：输入数组中所有元素均为 2 的幂（即 1, 2, 4, 8, 16, ...），且每个服务器可重复使用（题干中“server[1] 和 server[3]”暗示索引可复用，结合示例 getMinServers(10, [1, 1, 2, 4, 8, 16]) → 2 可验证：2 + 8 = 10，对应两个服务器）。注意：虽然数组含重复值（如两个 1），但题目逻辑上更倾向将其视为无限供应的面额集合——因为若仅限单次使用，[1, 1, 2, 4, 8] 中 10 = 2 + 8 已成立，无需依赖重复 1；而算法设计也默认允许重复选取同一值（递归中 include 分支调用 findMinServers(load - _array[index], index) 而非 index + 1，明确表示可重复使用当前元素）。

✅ 正确解法：记忆化递归（DFS + 剪枝）

暴力枚举所有子集或嵌套循环（如两层 for）仅适用于固定数量选择（如“恰好选2个”），但本题要求最小数量不限，必须支持 1 个、2 个、3 个……直至全覆盖。因此，推荐采用自顶向下的记忆化搜索：

• 状态定义：findMinServers(remain, idx) 表示用 arr[idx..end] 中的元素（可重复）凑出剩余负载 remain 所需的最少服务器数；
• 选择策略：
  • ✅ 包含当前元素：1 + findMinServers(remain - arr[idx], idx) —— 使用它，并可再次使用它（idx 不递增）；
  • ✅ 排除当前元素：findMinServers(remain, idx + 1) —— 跳过它，尝试下一个；
• 边界条件：
  • remain === 0 → 成功，返回 0（无需更多服务器）；
  • remain → 失败，返回 <code>-1；
• 合并结果：取两种选择中有效解的最小值（注意 -1 的空值处理）。

⚠️ 关键细节：原答案中 _array.sort((a, b) => b - a) 为降序排列，虽不影响正确性，但非必需。由于 2 的幂天然有序，且算法本身不依赖顺序，升序或降序均可。但降序可能略微提升剪枝效率（大数优先尝试，更快触达 remain ）。

以下是优化后的完整实现（含记忆化，避免指数级重复计算）：

function getMinServers(expected_load, servers) {
    // 去重并升序排序（更符合直觉，且便于后续扩展）
    const uniqueServers = [...new Set(servers)].sort((a, b) => a - b);

    // 记忆化缓存：Map
    const memo = new Map();

    function dfs(remain, idx) {
        // 边界检查
        if (remain === 0) return 0;
        if (remain = uniqueServers.length) return -1;

        const key = `${remain},${idx}`;
        if (memo.has(key)) return memo.get(key);

        const curr = uniqueServers[idx];
        const include = dfs(remain - curr, idx); // 重复使用当前服务器
        const exclude = dfs(remain, idx + 1);     // 跳过当前服务器

        let result;
        if (include === -1 && exclude === -1) {
            result = -1;
        } else if (include === -1) {
            result = exclude;
        } else if (exclude === -1) {
            result = include + 1;
        } else {
            result = Math.min(include + 1, exclude);
        }

        memo.set(key, result);
        return result;
    }

    return dfs(expected_load, 0);
}

// 测试用例
console.log(getMinServers(10, [1, 1, 2, 4, 8, 16])); // 输出: 2 (2 + 8)
console.log(getMinServers(7, [1, 2, 4]));            // 输出: 3 (1 + 2 + 4)
console.log(getMinServers(3, [2]));                 // 输出: -1 （无法凑出）

? 为什么不能用贪心？（重要辨析）

你可能直觉想到“从最大服务器开始贪心选取”，例如 10 → 选 8，剩 2 → 选 2，共 2 台。在纯 2 的幂集合（如 [1,2,4,8,...]）下，贪心确实最优——这等价于整数的二进制拆分（每个数有唯一二进制表示，1 的个数即最少服务器数）。但本题数组含重复值（如 [1,1,2,4,8]）且未声明“无限供应”，严格来说属于有界硬币问题。然而，示例 getMinServers(10, [1, 1, 2, 4, 8, 16]) 返回 2，证实了 8+2 合法，说明至少有两个 2 或 2 可复用。因此，题目隐含“每个容量值无限供应”，此时贪心成立，但面试中建议仍用通用 DP 解法体现工程严谨性。

✅ 总结

• 核心洞察：问题 = 无限硬币找零的最小硬币数，面额为 2 的幂；
• 最优解法：记忆化 DFS，时间复杂度 O(L × N)（L 为 expected_load，N 为去重后服务器种类数）；
• 避坑提示：勿用多层 for 循环（仅支持固定长度组合）；勿忽略 remain === 0 的终止条件；务必处理 -1 的传播逻辑；
• 进阶思考：若服务器数量有限（如每个容量最多用一次），则需转为 0-1 背包变体，状态改为 dp[i][w] = min servers using first i types to make w。

掌握此模型，即可从容应对各类“最小组合数凑目标值”面试题。