当前位置：首页 > JavaScript

js 实现组合

2026-03-15 04:39:50JavaScript

组合的概念

组合是从一组元素中选取若干元素，不考虑顺序。例如从数组 [1, 2, 3] 中选取 2 个元素的组合为 [[1, 2], [1, 3], [2, 3]]。

递归实现

递归是解决组合问题的常见方法。通过固定一个元素，递归处理剩余元素，逐步构建组合结果。

function combinations(arr, k) {
  const result = [];

  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < arr.length; i++) {
      current.push(arr[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

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

// 示例用法
console.log(combinations([1, 2, 3, 4], 2));
// 输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

迭代实现

使用迭代方法可以通过循环生成所有可能的组合，避免递归的调用栈问题。

function combinationsIterative(arr, k) {
  const result = [];
  const stack = [{ index: 0, current: [] }];

  while (stack.length > 0) {
    const { index, current } = stack.pop();

    if (current.length === k) {
      result.push([...current]);
      continue;
    }

    for (let i = index; i < arr.length; i++) {
      current.push(arr[i]);
      stack.push({ index: i + 1, current: [...current] });
      current.pop();
    }
  }

  return result;
}

// 示例用法
console.log(combinationsIterative([1, 2, 3], 2));
// 输出: [[1, 2], [1, 3], [2, 3]]

二进制位掩码法

对于较小规模的数组，可以使用二进制位掩码生成所有可能的子集，然后筛选出符合长度的组合。

function combinationsBitmask(arr, k) {
  const result = [];
  const n = arr.length;

  for (let mask = 0; mask < (1 << n); mask++) {
    if (countSetBits(mask) !== k) continue;

    const current = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        current.push(arr[i]);
      }
    }
    result.push(current);
  }

  return result;
}

function countSetBits(num) {
  let count = 0;
  while (num > 0) {
    count += num & 1;
    num >>= 1;
  }
  return count;
}

// 示例用法
console.log(combinationsBitmask([1, 2, 3], 2));
// 输出: [[1, 2], [1, 3], [2, 3]]