当前位置：首页 > JavaScript

js实现组合

2026-03-14 07:19:44JavaScript

组合的概念

组合是从给定集合中选择若干元素，不考虑顺序的数学操作。在JavaScript中实现组合通常涉及递归或迭代方法生成所有可能的子集。

递归实现组合

递归方法通过逐步缩小问题规模生成组合，适用于元素数量较少的情况。

function combinationsRecursive(arr, k) {
  if (k === 0 || k > arr.length) return [[]];
  if (k === arr.length) return [arr.slice()];

  const [first, ...rest] = arr;
  const withoutFirst = combinationsRecursive(rest, k);
  const withFirst = combinationsRecursive(rest, k - 1).map(comb => [first, ...comb]);

  return [...withFirst, ...withoutFirst];
}

迭代实现组合

迭代方法使用位运算或循环生成组合，适合处理较大数据集。

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;
    }
    if (index >= arr.length) continue;

    stack.push({ index: index + 1, current: [...current, arr[index]] });
    stack.push({ index: index + 1, current: [...current] });
  }

  return result;
}

库函数实现

使用现成的库函数可以简化组合生成过程，如Lodash的_.combinations。

const _ = require('lodash');
const result = _.combinations([1, 2, 3, 4], 2);

性能优化建议

对于大规模数据组合计算，考虑使用生成器函数或记忆化技术减少内存消耗。

function* combinationsGenerator(arr, k) {
  function* helper(start, path) {
    if (path.length === k) yield path.slice();
    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      yield* helper(i + 1, path);
      path.pop();
    }
  }
  yield* helper(0, []);
}