77. 组合

77. 组合

代码

javascript

// 77. 组合：https://leetcode.cn/problems/combinations/
// 输入：n = 4, k = 2
// 输出：[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

export function combinations (n, k) {
  const ans = []
  const dfs = (cur, temp) => {
    if (temp.length + (n - cur + 1) < k) {
      return
    }
    if (temp.length === k) {
      ans.push(temp)
      return
    }
    dfs(cur + 1, [...temp, cur])
    dfs(cur + 1, temp)
  }
  dfs(1, [])
  return ans
}

typescript

// 77. 组合：https://leetcode.cn/problems/combinations/
// 输入：n = 4, k = 2
// 输出：[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

export function combinations (n: number, k: number): number[][] {
  const ans: number[][] = []
  const dfs = (cur: number, temp: number[]) => {
    if (temp.length + (n - cur + 1) < k) {
      return
    }
    if (temp.length === k) {
      ans.push(temp)
      return
    }
    dfs(cur + 1, [...temp, cur])
    dfs(cur + 1, temp)
  }
  dfs(1, [])
  return ans
}

测试代码

test

import { expect, test } from 'vitest'
import { combinations } from './typescript.ts'
import { combinations as combinationsJs } from './javascript.js'

test(`combinations`, () => {
  expect(combinations(4, 2)).toEqual([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
  expect(combinations(1, 1)).toEqual([[1]])
})

test(`combinationsJs`, () => {
  expect(combinationsJs(4, 2)).toEqual([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
  expect(combinationsJs(1, 1)).toEqual([[1]])
})