77.组合.md

77.组合

/*
 * @lc app=leetcode.cn id=77 lang=typescript
 *
 * [77] 组合
 */

// @lc code=start
function combine(n: number, k: number): number[][] {}
// @lc code=end

解法 1: 迭代

function combine(n: number, k: number): number[][] {
  let result: number[][] = [[]]
  for (let i = 0; i < k; i++) {
    let tmp = result
    result = []
    for (let j = 0; j < tmp.length; j++) {
      const arr = tmp[j]
      for (let l = arr.length && arr[arr.length - 1]; l < n - k + i + 1; l++) {
        result.push([...arr, l + 1])
      }
    }
  }
  return result
}

解法 2: 递归

function combine(n: number, k: number): number[][] {
  const helper = (n: number, k: number) => {
    if (k === 0) return [[]]

    let result: number[][] = []
    for (const item of helper(n, k - 1)) {
      const start = item.length && item[item.length - 1]

      for (let j = start; j < n + k; j++) {
        result.push([...item, j + 1])
      }
    }

    return result
  }

  return helper(n - k, k)
}

解法 3: 回溯

function combine(n: number, k: number): number[][] {
  const res: number[][] = []
  const dfs = (path: number[] = [], depth = 0) => {
    if (depth === k) return res.push([...path])

    for (let i = path[path.length - 1] ?? 0; i < n; i++) {
      path.push(i + 1)
      dfs(path, depth + 1)
      path.pop()
    }
  }
  dfs()
  return res
}

Case

test.each([
  {
    input: { n: 4, k: 2 },
    output: [
      [2, 4],
      [3, 4],
      [2, 3],
      [1, 2],
      [1, 3],
      [1, 4],
    ],
  },
  { input: { n: 1, k: 1 }, output: [[1]] },
])('input: n = $input.n, k = $input.k', ({ input: { n, k }, output }) => {
  expect(combine(n, k)).toIncludeSameMembers(output)
})