如何在JavaScript中获取n长度数组的所有k长度组合？

给定一个长度为n的数组，需要生成其中所有包含k个元素的组合（不考虑元素顺序，即[1,2,3]和[2,1,3]视为同一个组合，只保留一种）。例如输入数组[1,2,3,...,12]，要得到所有长度为4的子组合，包括连续的[1,2,3,4]、非连续的[1,2,4,5]等。

你当前尝试的代码如下：

function getCombinations(k, n) {
  const array = new Array(n)
  array.forEach((x, i) => {
    array[i] = i + 1
  })
  const results = []
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      let l = k
      const result = []
      while (l--) {
        result.push(j) // ???
      }
    }
  }
}

解决方案：递归回溯法 #

递归回溯是解决组合问题的经典思路，核心逻辑是：每次从数组中选择一个元素，然后在该元素之后的剩余元素中继续选择k-1个元素（避免重复组合），直到选够k个元素时将当前组合存入结果集。

实现代码如下：

function getCombinations(k, n) {
  // 生成初始数组 [1,2,...,n]
  const array = Array.from({ length: n }, (_, i) => i + 1);
  const results = [];

  // 递归回溯函数
  function backtrack(start, currentCombination) {
    // 当当前组合长度等于k时，存入结果
    if (currentCombination.length === k) {
      results.push([...currentCombination]);
      return;
    }

    // 从start位置开始遍历，避免重复组合
    for (let i = start; i < array.length; i++) {
      // 选择当前元素
      currentCombination.push(array[i]);
      // 递归：在当前元素之后的位置继续选剩余元素
      backtrack(i + 1, currentCombination);
      // 回溯：移除当前元素，尝试下一个选项
      currentCombination.pop();
    }
  }

  // 启动回溯，从索引0开始，初始组合为空
  backtrack(0, []);
  return results;
}

// 示例调用：生成n=12，k=4的所有组合
const combinations = getCombinations(4, 12);
console.log(combinations);

代码解释 #

• 数组生成：用Array.from替代原代码的forEach，更简洁地生成[1,2,...,n]。
• 回溯函数：
  • start参数控制遍历的起始位置，确保每次选择的元素都在之前选中元素的后面，避免生成重复的组合（比如不会同时出现[1,2,3]和[2,1,3]）。
  • 当currentCombination的长度等于k时，通过[...currentCombination]创建副本存入结果，避免后续修改影响已存入的组合。
  • 递归调用后执行pop()，撤销当前选择，继续尝试下一个元素。

迭代实现（可选） #

如果不想用递归，也可以用迭代的方式生成组合，核心是逐步构建长度为1、2...k的组合：

function getCombinations(k, n) {
  const array = Array.from({ length: n }, (_, i) => i + 1);
  let results = array.map(item => [item]);

  // 逐步将组合长度从1扩展到k
  for (let len = 2; len <= k; len++) {
    const newResults = [];
    // 遍历现有组合，在每个组合的最后一个元素之后添加新元素
    results.forEach(comb => {
      const lastIndex = array.indexOf(comb[comb.length - 1]);
      for (let i = lastIndex + 1; i < array.length; i++) {
        newResults.push([...comb, array[i]]);
      }
    });
    results = newResults;
  }

  return results;
}

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