LeetCode 46. 全排列

46. 全排列

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

思路：参考b站视频题解 [算法教程] 全排列_哔哩哔哩_bilibili

• 将每个元素分别都固定一次到首位置上

• 以 p+1为起点，q 为终点的新子数组，再次进行下一层新子数组的递归

• 注意：go中使用 copy() 方法时，要提前分配好数组长度len，否则copy结果为空

时间复杂度 / 空间复杂度：

// 参考b站视频：https://www.bilibili.com/video/BV1dx411S7WR?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4
var res [][]int
 
func permute(nums []int) [][]int {
	res = make([][]int, 0)
	perm(nums, 0, len(nums)-1)
	return res
}
 
func perm(nums []int, p, q int) {
	if p == q {
		tmpNums := make([]int, len(nums))   // 注意：使用copy()方法时，要提前分配好数组长度len，否则copy结果为空
		copy(tmpNums, nums)
		res = append(res, tmpNums)
		return
	}
 
	for i := p; i < len(nums); i++ {
		nums[p], nums[i] = nums[i], nums[p] // 将每个元素分别都固定一次到首位置上
		perm(nums, p+1, q)                  // 以p+1为起点，q为终点的新子数组，再次进行下一层新子数组的递归
		nums[p], nums[i] = nums[i], nums[p] // 还原回溯，避免上一层递归结果影响到下一层递归
	}
}

另外还有通过dfs/bfs的方式生成全排列组合，待研究...