当前位置：首页 > JavaScript

js 实现组合

2026-04-06 22:13:20JavaScript

实现组合的基本概念

组合是从一组元素中选出若干元素，不考虑顺序。例如从数组 [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], 2)); // [[1, 2], [1, 3], [2, 3]]

迭代实现组合

迭代方法利用栈模拟递归过程，避免递归可能导致的堆栈溢出问题。

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* combinationsGenerator(arr, k, start = 0, current = []) {
  if (current.length === k) {
    yield [...current];
    return;
  }

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

// 示例
const gen = combinationsGenerator([1, 2, 3], 2);
console.log([...gen]); // [[1, 2], [1, 3], [2, 3]]

处理重复元素的组合

如果输入数组包含重复元素，需要去重处理。

js 实现组合

function combinationsWithDup(arr, k) {
  arr.sort((a, b) => a - b);
  const result = [];

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

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

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

// 示例
console.log(combinationsWithDup([1, 2, 2, 3], 2)); // [[1, 2], [1, 3], [2, 2], [2, 3]]