77. 组合 | LeetCode算法题解

题目描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路

深度优先搜索。维护一个当前数组，和一个剩余元素数组，每次把剩余元素一个个加入到当前数组中，若当前数组长度为 k 则得到一个有效组合。
可适当剪枝。

解法

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
const combine = (n, k) => {
  const result = [];

  /**
   *
   * @param {number[]} current 当前生成数组
   * @param {number[]} rest 剩余可加入元素
   */
  const dfs = (current, rest) => {
    if (current.length === k) {
      result.push(current);
      return;
    }

    // 剪枝
    if (current.length + rest.length < k) {
      return;
    }

    rest.forEach((item, index) => {
      dfs([...current, item], [...rest.slice(index + 1)]);
    });
  };

  dfs(
    [],
    Array(n)
      .fill()
      .map((_, i) => i + 1),
  );

  return result;
};