Heading

46.全排列 (opens new window)

Tags: algorithms linkedin microsoft backtracking

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (79.07%)
• Likes: 2846
• Dislikes: -
• Total Accepted: 1M
• Total Submissions: 1.3M
• Testcase Example: '[1,2,3]'

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

 

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

 

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 * 回溯
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = []
  const dfs = (current, arr) => {
    if (arr.length === 0) {
      result.push(current)
    }

    for (let i = 0; i < arr.length; i++) {
      dfs(
        [...current, arr[i]],
        arr.filter((item, index) => index !== i),
      )
    }
  }
  dfs([], nums)
  return result
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 * 递归
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  if (nums.length === 0) {
    return []
  }
  if (nums.length === 1) {
    return [nums]
  }

  const [first, ...rest] = nums
  const restArrange = permute(rest)

  const result = restArrange.reduce((acc, item) => {
    for (let i = 0; i <= item.length; i++) {
      const tmp = [...item]
      tmp.splice(i, 0, first)
      acc.push(tmp)
    }
    return acc
  }, [])

  return result
}
// @lc code=end