132 - 46 全排列

题目

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

解答

感觉可以用递归做。。

python库

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

Runtime: 36 ms, faster than 99.74% of Python3 online submissions for Permutations.

Memory Usage: 13.9 MB, less than 5.36% of Python3 online submissions for Permutations.

回溯算法

https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

第一反应就是，一个个摁住数字，然后排序。回溯算法也这样

46-1.png

就是对这个树进行深度优先遍历。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        used = [False]*len(nums)
        res = []
        Solution.__dfs(self, nums, 0, [], used, res)
        return res

    def __dfs(self, nums: List[int], index: int, pre: [int], used: [int], res: [int]):
        if index == len(nums):
            res.append(pre.copy())
            return

        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                pre.append(nums[i])

                Solution.__dfs(self, nums, index+1, pre, used, res)

                used[i] = False
                pre.pop()

Runtime: 44 ms, faster than 91.26% of Python3 online submissions for Permutations.

Memory Usage: 13.8 MB, less than 5.36% of Python3 online submissions for Permutations.

var permute = function(nums) {
  if (nums.length === 0) {
    return []
  }
  let used = new Array(nums.length)
  for (let i = 0; i < used.length; i++) {
    used[i] = false
  }
  let res = []
  const dfs = function(nums, index, pre, used, res) {
    if (index === nums.length) {
      res.push(pre.slice())
      return
    }
    for (let i in nums) {
      if (!used[i]) {
        used[i] = true
        pre.push(nums[i])
        dfs(nums, index + 1, pre, used, res)
        used[i] = false
        pre.pop()
      }
    }
  }
  dfs(nums, 0, [], used, res)
  return res
};

Runtime: 72 ms, faster than 45.94% of JavaScript online submissions for Permutations.

Memory Usage: 36.4 MB, less than 48.00% of JavaScript online submissions for Permutations.

https://leetcode.com/problems/permutations/discuss/312267/go%3A-backtrack

func permute(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    res := make([][]int, 0)
    dfs(nums, nil, &res)
    return res
}
func dfs(nums []int, pre []int, res *[][]int) {
    if len(nums) == 0 {
        *res = append(*res, append([]int{}, pre...))
        return
    }
    for i := range nums {
        dfs(append(append([]int{}, nums[0:i]...), nums[i+1:]...), append(pre, nums[i]), res)
    }
}

Runtime: 4 ms, faster than 92.03% of Go online submissions for Permutations.

Memory Usage: 7 MB, less than 100.00% of Go online submissions for Permutations.

递归

https://leetcode.com/problems/permutations/discuss/277169/my-go-solution-backtracking

func permute(nums []int) [][]int {
    var ret [][]int
    var helper func(int)
    helper = func(k int) {
        if k == len(nums) {
            tmp := make([]int, len(nums))
            copy(tmp, nums)
            ret = append(ret, tmp)
            return
        }
        for i := k; i < len(nums); i++ {
            nums[i], nums[k] = nums[k], nums[i]
            helper(k + 1)
            nums[i], nums[k] = nums[k], nums[i]
        }
    }
    helper(0)
    return ret
}

Runtime: 4 ms, faster than 92.03% of Go online submissions for Permutations.

Memory Usage: 7 MB, less than 100.00% of Go online submissions for Permutations.

var permute = function(nums) {
  if (nums.length === 0) {
    return []
  }
  let res = []
  const helper = function(k) {
    if (k === nums.length) {
      res.push(nums.slice())
      return
    }
    for (let i = k; i < nums.length; i++) {
      [nums[i], nums[k]] = [nums[k], nums[i]]
      helper(k + 1);
      [nums[i], nums[k]] = [nums[k], nums[i]]
    }
  }
  helper(0)
  return res
};

Runtime: 68 ms, faster than 68.65% of JavaScript online submissions for Permutations.

Memory Usage: 36.8 MB, less than 24.00% of JavaScript online submissions for Permutations.