77.组合

链接：77.组合
难度：Medium
标签：回溯
简介：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

题解 1 - typescript

• 编辑时间：2020-09-08
• 执行用时：600ms
• 内存消耗：46.6MB
• 编程语言：typescript
• 解法介绍：回溯递归，利用 set 进行校验。

function combine(n: number, k: number): number[][] {
  const arr: number[] = [-1];
  const ans: number[][] = [];
  const used = new Set<number>();
  find();
  return ans;
  function find() {
    if (used.size === k) {
      ans.push(arr.slice(1));
      return;
    }
    for (let i = 1; i <= n; i++) {
      if (!used.has(i) && arr[arr.length - 1] < i) {
        used.add(i);
        arr.push(i);
        find();
        arr.pop();
        used.delete(i);
      }
    }
  }
}

题解 2 - typescript

• 编辑时间：2021-08-20
• 执行用时：164ms
• 内存消耗：46.5MB
• 编程语言：typescript
• 解法介绍：dfs。

function combine(n: number, k: number): number[][] {
  const set = new Set<number>();
  const ans: number[][] = [];
  dfs();
  return ans;
  function dfs(list: number[] = [], min = 1) {
    if (list.length === k) {
      ans.push(list.slice());
      return;
    }
    if (min > n) return;
    for (let i = min; i <= n; i++) {
      if (set.has(i)) continue;
      list.push(i);
      set.add(i);
      dfs(list, i + 1);
      set.delete(i);
      list.pop();
    }
  }
}

题解 3 - javascript

• 编辑时间：2021-09-20
• 执行用时：116ms
• 内存消耗：43.4MB
• 编程语言：javascript
• 解法介绍：dfs。

function combine(n: number, k: number): number[][] {
  const ans: number[][] = [];
  for (let i = 1; i <= n; i++) dfs(i);
  return ans;
  function dfs(num: number, list: number[] = []): void {
    if (num === n + 1) return;
    list.push(num);
    if (list.length === k) ans.push(list.slice());
    else for (let i = num + 1; i <= n; i++) dfs(i, list);
    list.pop();
  }
}

题解 4 - typescript

• 编辑时间：2020-09-08
• 执行用时：140ms
• 内存消耗：46.2MB
• 编程语言：typescript
• 解法介绍：回溯+剪枝。

function combine(n: number, k: number): number[][] {
  const ans: number[][] = [];
  dfs();
  return ans;
  function dfs(cur: number = 1, arr: number[] = []): void {
    // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
    if (arr.length + (n - cur + 1) < k) return;
    if (arr.length === k) {
      ans.push(arr);
      return;
    }
    dfs(cur + 1, [...arr, cur]);
    dfs(cur + 1, arr);
  }
}