实现N选X组合生成函数（迭代/递归方案均可）

需求描述 #

给定一个包含N个元素的列表，例如：

const list = [0, 1, 2, ...(N-1)];

需要实现函数findAllCombinations(x, list)，生成列表中所有X个元素的组合，对应数学中的组合数(N choose X)。

已知X=2时的迭代写法示例：

const findAllCombinations = (x, list) => {
    for(let i = 0; i < list.length; i++){
      for(let j = i+1; j < list.length; j++){
           // N选2的逻辑
       }
     }
};

但无法将此逻辑扩展到通用的N选X场景，优先需要迭代式实现，也接受递归方案。

错误的递归尝试及问题 #

以下是存在缺陷的递归实现：

const combine = (x, list) => {
    
    // 注：N = list.length

    if(list.length < x){
        throw new Error('not enough elements to combine.');
    }

    if (x < 1) {
        return [];
    }

    const ret = [];

    for(let v of combine(x-1, list.slice(1))){
        ret.push([list[0], ...v]);
    }

    return ret;
}
    
console.log(
   combine(3, ['a','b','c','d'])
)

问题：该代码仅生成包含列表第一个元素的组合（如[a,b,c]、[a,b,d]、[a,c,d]），漏掉了不包含第一个元素的组合[b,c,d]，无法得到(4 choose 3)=4的完整结果。同时边界条件处理错误：当x=0时，正确结果应为[[]]（因为N choose 0=1），但当前代码返回空数组。

正确的递归实现 #

修正边界条件，并补充“不包含当前元素”的递归分支：

const combine = (x, list) => {
    const n = list.length;
    
    // 边界条件：元素不足，抛出错误
    if (n < x) {
        throw new Error('not enough elements to combine.');
    }
    
    // 边界条件：选0个元素，返回包含空数组的列表
    if (x === 0) {
        return [[]];
    }
    
    // 边界条件：选全部元素，返回包含原列表的列表
    if (x === n) {
        return [list.slice()];
    }
    
    const result = [];
    
    // 情况1：包含当前第一个元素，递归处理剩余元素选x-1个
    for (const subset of combine(x - 1, list.slice(1))) {
        result.push([list[0], ...subset]);
    }
    
    // 情况2：不包含当前第一个元素，递归处理剩余元素选x个
    result.push(...combine(x, list.slice(1)));
    
    return result;
};

测试验证：

console.log(combine(0, [1,2,3])); // [[]] → 正确
console.log(combine(1, [1,2,3])); // [[1],[2],[3]] → 正确
console.log(combine(2, [1,2,3])); // [[1,2],[1,3],[2,3]] → 正确
console.log(combine(3, [1,2,3])); // [[1,2,3]] → 正确
console.log(combine(3, ['a','b','c','d'])); // [[a,b,c],[a,b,d],[a,c,d],[b,c,d]] → 正确

迭代式实现（回溯法） #

通过回溯的迭代方式生成所有组合，避免递归调用：

const findAllCombinations = (x, list) => {
    const n = list.length;
    if (n < x) throw new Error('not enough elements to combine.');
    if (x === 0) return [[]];
    if (x === n) return [list.slice()];
    
    const result = [];
    const stack = [];
    
    // 初始化栈：每个元素保存当前起始索引、当前组合
    stack.push({ start: 0, current: [] });
    
    while (stack.length > 0) {
        const { start, current } = stack.pop();
        
        // 如果当前组合长度等于x，加入结果
        if (current.length === x) {
            result.push(current);
            continue;
        }
        
        // 从start开始遍历，避免重复组合
        for (let i = start; i < n; i++) {
            // 剪枝：剩余元素数量足够时才继续
            if ((n - i - 1) >= (x - current.length - 1)) {
                stack.push({
                    start: i + 1,
                    current: [...current, list[i]]
                });
            }
        }
    }
    
    return result;
};

测试验证：

console.log(findAllCombinations(2, [0,1,2,3])); 
// 输出：[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]] → 正确

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