老卫带你学---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]]
1
2
3
4

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
1
2
3
4

示例 3：

输入：nums = [1]
输出：[[1]]
1
2
3
4

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
1
2
3
4
5

解决：

dfs递归回溯

var res [][]int

// 标准开局
func permute(nums []int) [][]int {
	res = make([][]int,0)
	dfs(0,nums)
	return res
}

func dfs(x int,nums []int){
	if x==len(nums)-1{ //如果搜到最后一个，就代表搜完
		tmp := make([]int,len(nums)) 
		copy(tmp, nums) //go里面需要注意copy
		res = append(res, tmp)
		return
	}
	for i :=x;i<len(nums);i++{ //注意从x开始，代表固定一个
		nums[i], nums[x] = nums[x],nums[i]
		dfs(x+1,nums)  //递归，固定下一个
		nums[i], nums[x] = nums[x],nums[i]
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22