如何确定由恰好k块长短木板组成的板面的所有可能长度？

问题描述 #

我们需要用恰好k块木板拼接成一块木质板面，现有两种规格的木板：短板（记为shorter）和长板（记为longer），要找出这个板面所有可能的总长度。

核心思路 #

本质上就是枚举所有可能的木板组合：我们可以使用0到k块短板，剩下的k - 短板数量块就是长板，计算每种组合的总长度即可。需要注意的是，如果shorter和longer的长度相同，所有组合的结果都是一样的，最终只会得到一个唯一长度。

解决方案实现 #

递归版本

通过递归逐步选择短板或长板，直到用完所有k块木板，将结果存入集合自动去重：

// 对外调用的入口方法
getAllLengths(k, shorter, longer) {
    Set lengths = new Set() // 用集合存储结果，自动去重
    getAllLengthsHelper(k, 0, shorter, longer, lengths)
    return lengths
}

// 递归辅助方法，处理剩余木板数和当前总长度
getAllLengthsHelper(remainingPlanks, currentTotal, shorter, longer, lengths) {
    // 木板用完了，记录当前总长度
    if (remainingPlanks == 0) {
        lengths.add(currentTotal)
        return
    }
    // 选择一块短板，继续递归
    getAllLengthsHelper(remainingPlanks - 1, currentTotal + shorter, shorter, longer, lengths)
    // 选择一块长板，继续递归
    getAllLengthsHelper(remainingPlanks - 1, currentTotal + longer, shorter, longer, lengths)
}

迭代版本（更高效直观）

直接遍历所有可能的短板数量，计算对应总长度，同样用集合去重：

getAllLengths(k, shorter, longer) {
    Set lengths = new Set()
    // 遍历0到k块短板的所有情况
    for (int i = 0; i <= k; i++) {
        int totalLength = i * shorter + (k - i) * longer
        lengths.add(totalLength)
    }
    return lengths
}

补充说明 #

• 两种方法都用集合存储结果，目的是自动处理shorter == longer时的重复值，避免返回多个相同的长度。
• 迭代版本的时间复杂度是O(k)，比递归版本更高效，也更易于理解和调试，推荐优先使用。

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