前言
本系列文章为《leetcode》刷题笔记。
题目位置：力扣中国
项目位置：我的Github项目
题目
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路
方法一、回溯
这种题目明显是用回溯来做了，因为他的输出结果给的就是回溯的。
回溯的思路就是
- 先找一个路径出来，记录下来这个路径。
- 擦掉最后一次的查找记录，返回上一层
- 重新找倒数第二层，找到以后继续找下一层，直到找到一个新的路径
- 限定条件：每一层查找出来的数字都必须和其他不同
所以根据我的思路描述和上图，我的算法计划：
- 使用递归，这样每找一层，找下一层的操作就是调用自己
- 每层递归都用一个循环遍历原数组所有的元素，每遍历一个就判断一次是否和前面的数重复：所以我们需要一个for循环，需要一个判断用的函数checkIndex
- 递归就要有终止条件：这里的终止条件有三个
第一个：找到了完整的路径，为了防止进入下一次递归，立刻跳出当前也就是最后一层递归（也就是当前找的元素没有和前面的重合，而且当然找到的是最后一个元素）
if checkIndex(indexs, current) { continue } if current == len-1 { //保存找到的路径 }
第二个：上一层递归返回，而当前递归的循环已经遍历完了最后一个元素。比如下图的第二层循环已经遍历完了3，所以只能擦掉当前，继续返回了！
代码是：
for i := 0; i < len; i++ {//此时i==len-1， //... run(indexs, nums, newCurrent, len) indexs[current] = -1 }
ps: 有没有可能最后一层递归，所有元素都找遍了，都没有找到呢？不可能！因为前面的所有元素都不重复，递归层数和数组长度相等，所以完全不可能找不到。
时间复杂度 O(N^(N+1))： 因为一层循环是n，有n-1层循环嵌套
空间复杂度 O(h(n))：回溯的空间是动态生成的，如果不要求保留答案，只用输出的话那空间使用h(n),也就是深度。但是这里要求保存结果，就多申请了结果 * 深度 个空间。这是个概率论的题目，结果应该有h(n)!个（阶乘）。
方法二、Python3库函数
Python3 itertools 文档
直接调用库函数itertools.permutations即可
代码
Go
var ResRow [][]int func checkIndex(indexs []int, curret int) bool { for i := 0; i < curret; i++ { if indexs[i] == indexs[curret] { return true } } return false } func run(indexs []int, nums []int, current int, len int) { for i := 0; i < len; i++ { indexs[current] = nums[i] if checkIndex(indexs, current) { continue } if current == len-1 { res_col := make([]int, len) for i := 0; i < len; i++ { res_col[i] = indexs[i] } ResRow = append(ResRow,res_col) indexs[current] = -1 return } newCurrent := current + 1 run(indexs, nums, newCurrent, len) indexs[current] = -1 } } func permute(nums []int) [][]int { indexs := make([]int, len(nums)) //init num_indexs for i := 0; i < len(nums); i++ { indexs[i] = -1 } //run run(indexs, nums, 0, len(nums)) var tmpRow = ResRow ResRow = [][]int{} return tmpRow }
PS： 其实这一题的名字叫八皇后。
Python3
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: return list(itertools.permutations(nums))
