题目

给定一个不含重复数字的整数数组 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 中的所有整数 互不相同

注意：本题与主站 46 题相同

解题思路分析

1、回溯；时间复杂度O(n^n)，空间复杂度O(n*n!)

var res [][]int

func permute(nums []int) [][]int {
   res = make([][]int, 0)
   arr := make([]int, 0)
   visited := make(map[int]bool)
   dfs(nums, 0, arr, visited)
   return res
}

func dfs(nums []int, index int, arr []int, visited map[int]bool) {
   if index == len(nums) {
      temp := make([]int, len(arr))
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   for i := 0; i < len(nums); i++ {
      if visited[i] == false {
         arr = append(arr, nums[i])
         visited[i] = true
         dfs(nums, index+1, arr, visited)
         arr = arr[:len(arr)-1]
         visited[i] = false
      }
   }
}

2、递归；时间复杂度O(n!)，空间复杂度O(n*n!)

func permute(nums []int) [][]int {
   if len(nums) == 1 {
      return [][]int{nums}
   }
   res := make([][]int, 0)
   for i := 0; i < len(nums); i++ {
      tempArr := make([]int, len(nums)-1)
      copy(tempArr[0:], nums[:i])
      copy(tempArr[i:], nums[i+1:])
      arr := permute(tempArr)
      for _, v := range arr {
         res = append(res, append(v, nums[i]))
      }
   }
   return res
}

3、回溯；时间复杂度O(n!)，空间复杂度O(n*n!)

var res [][]int

func permute(nums []int) [][]int {
   res = make([][]int, 0)
   arr := make([]int, len(nums))
   dfs(nums, 0, arr)
   return res
}

func dfs(nums []int, index int, arr []int) {
   if index == len(nums) {
      temp := make([]int, len(arr))
      copy(temp, arr)
      res = append(res, temp)
      return
   }
   for i := index; i < len(nums); i++ {
      arr[index] = nums[i]
      nums[i], nums[index] = nums[index], nums[i]
      dfs(nums, index+1, arr)
      nums[i], nums[index] = nums[index], nums[i]
   }
}

总结

Medium题目，题目同leetcode 46.全排列、面试题08.07.无重复字符串的排列组合