【刷题日记】剑指 Offer II 083. 没有重复元素集合的全排列

本次刷题日记的第 35 篇，力扣题为：剑指 Offer II 083. 没有重复元素集合的全排列 ，中等

一、题目描述：

题目内容少，总感觉有坑，此处需谨慎，需要注意多加思考和分析

二、这道题考察了什么思想？你的思路是什么？

咱们可以看一下这个题具体是需要我们做些什么呢？

• 题目要我们对于一个没有重复数字的数组进行全排列，那么什么是全排列呢？

对于这个题，简单来说，咱们就是取题目中给出的数组中的每一个元素，对于任意顺序来排列起来成为一个结果，所有结果加起来，就是全排列了

乍一听，咋感觉像是排列组合，其实只能说是类似吧

咱们画一个简图来感受一下 题目中给出的示例，全排列是怎么组合起来的

通过上面的模拟，我们的思路就是

• 选择数字 1 进行递归，然后对 1 标记已使用，tmp 中 加入 1
• 选择数字 2 进行赌鬼，然后对 2 进行标记，tmp 加入 2
• 同理加入 3 ，最终将结果 tmp = 1 ，2 ，3 加入到结果集
• 回溯递归，tmp 去掉尾巴的元素，直到 将每一种组合都加入到结果中，则咱们就完成了本次的全排列

根据这个思路，实际上就是让 nums 中的元素，能够在每一个位置上都能有机会出现，咱们就能实现让这个数字通过任意顺序排列起来，将所有的结果都加入到集合中，这就是一个全排列

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要注意使用回溯的逻辑和细节，一层一层的递归进去

tmp 临时数组也不断的追加数字，然后退出一层递归的时候，同时也将 tmp 尾巴的数字去掉

func permute(nums []int) [][]int {
  n := len(nums)
  var res [][]int
  var tmp []int
    // 用于校验数字中某个索引对应的数字是否已经在 tmp 数组中
  vis := make([]bool, n)
    //递归输入的参数表示我们使用数字的第几个数组作为全排列的第一个数字
  var dfs func(cnt int)
  dfs = func(cnt int) {
        // 当传入的数字已经不在nums数组范围内了，那么就直接将当前结果加入到结果集中，并退出，回退到上一层
    if cnt == n {
      res = append(res, append([]int{}, tmp...))
      return
    }
        // 本层开始 遍历 nums 数组，对于已经遍历过的就不在做处理
    for i := 0; i < n; i++ {
      if vis[i] {
        continue
      }
      tmp = append(tmp, nums[i])
      vis[i] = true
            // 若需要将该数字加入到结果集中，那么就从此处开始进行递归
      dfs(cnt + 1)
            // 退出递归后，则去掉 tmp 临时数组的最后一位
      tmp = tmp[:len(tmp)-1]
      vis[i] = false
    }
  }
  dfs(0)
  return res
}

这个回溯的方式，有没有觉得还是很有意思的，一层一层的递归进去，tmp 也不断的增加元素，退出递归的时候，本次的 tmp 已经加入到结果集中了

然后 tmp 去掉尾巴的数字，又可以继续进入下一次遍历了

四、总结：

咱们先来查看一下这种实现的空间复杂度是多少呢？ 咱们的递归的时候，是需要消耗栈上的空间的，根据本次实现的递归调用深度来看，空间复杂都市 O(n)

那么时间复杂度也是 o(n) 吗？ xdm 可以思考一下 具体是 O(n) 呢，还是 O(n*n!) 呢？

原题地址：剑指 Offer II 083. 没有重复元素集合的全排列

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~