JavaScript数组组合求解：选X个元素和为N的所有可重复组合

核心思路：回溯+剪枝+去重 #

要找固定长度X、和为N且元素可重复的组合，同时避免生成重复排列（比如[1000,500,100,100]和[500,1000,100,100]属于同一组合），可以按以下步骤实现：

1. 数组预排序
   先将给定数组按降序排列，递归选择元素时只允许选当前元素或更小的元素，从根源上避免重复组合生成。比如选了1000之后，后续只能选<=1000的元素，不会出现逆序的重复排列。

2. 回溯遍历+剪枝优化
   用递归逐步构建组合，同时加入剪枝条件减少无效遍历：

   • 递归参数：已选元素列表、当前累计和、当前可选元素的起始索引（控制不选比当前元素大的，避免重复）、还需要选的元素个数。
   • 终止条件：当还需要选的元素个数为0时，若当前累计和等于N，就将该组合加入结果列表。
   • 剪枝逻辑：遍历元素时，若当前元素乘以剩余需要选的个数大于剩余所需总和，或当前元素加入后总和超过N，直接跳过；若当前元素加入后，即使剩余位置都选该元素总和仍达不到N，也跳过（数组降序，后续元素更小，更无法满足）。

JavaScript代码实现 #

function findCombinations(coins, X, N) {
    // 降序排序，避免重复组合
    const sortedCoins = [...coins].sort((a, b) => b - a);
    const result = [];

    // 回溯函数
    function backtrack(currentCombination, currentSum, startIndex, remainingCount) {
        // 终止条件：选够X个元素且和为N
        if (remainingCount === 0) {
            if (currentSum === N) {
                result.push([...currentCombination]);
            }
            return;
        }

        for (let i = startIndex; i < sortedCoins.length; i++) {
            const num = sortedCoins[i];
            const remainingSum = N - currentSum;

            // 剪枝：当前元素加入后总和超N，跳过
            if (currentSum + num > N) continue;
            // 剪枝：即使剩余位置都选当前元素，总和仍不够N，跳过
            if (currentSum + num * remainingCount < remainingSum) continue;

            // 选择当前元素
            currentCombination.push(num);
            // 递归：允许重复选当前元素，剩余个数减1
            backtrack(currentCombination, currentSum + num, i, remainingCount - 1);
            // 回溯，撤销选择
            currentCombination.pop();
        }
    }

    backtrack([], 0, 0, X);
    return result;
}

// 测试示例
const coins = [1000, 500, 400, 300, 200, 100];
console.log(findCombinations(coins, 4, 1700));
// 注：你提供的示例中[500,400,400,490]包含数组外元素490，属于笔误，代码不会生成该组合

关键细节说明 #

• 去重逻辑：通过降序排序+递归时从startIndex开始遍历，确保组合内元素非递增，不会生成不同顺序的重复组合。
• 剪枝效率：提前跳过不可能满足条件的元素，避免不必要的递归调用，大幅提升性能，尤其是当X和N较大时。

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