47. 全排列 II

47. 全排列 II

代码

javascript

// 47. 全排列 II：https://leetcode.cn/problems/permutations-ii/description/
// 输入：[1,1,2]
// 输出：[[1,1,2],[1,2,1],[2,1,1]]

export function permutationsIi (nums) {
  const res = []
  nums = nums.sort((a, b) => a - b)
  function dfs (curList, list) {
    if (curList.length === nums.length) {
      res.push(curList)
      return
    }
    for (let i = 0, len = list.length; i < len; i++) {
      const newList = [...list]
      dfs([...curList, ...newList.splice(i, 1)], newList)
      while (i + 1 < len && list[i + 1] === list[i]) {
        i++
      }
    }
  }
  dfs([], nums)
  return res
}

typescript

// 47. 全排列 II：https://leetcode.cn/problems/permutations-ii/description/
// 输入：[1,1,2]
// 输出：[[1,1,2],[1,2,1],[2,1,1]]

export function permutationsIi (nums: number[]): number[][] {
  const res: number[][] = []
  nums = nums.sort((a, b) => a - b)
  function dfs (curList: number[], list: number[]) {
    if (curList.length === nums.length) {
      res.push(curList)
      return
    }
    for (let i = 0, len = list.length; i < len; i++) {
      const newList = [...list]
      dfs([...curList, ...newList.splice(i, 1)], newList)
      while (i + 1 < len && list[i + 1] === list[i]) {
        i++
      }
    }
  }
  dfs([], nums)
  return res
}

测试代码

test

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

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

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