老卫带你学---leetcode刷题(47. 全排列 II)

47. 全排列 II

问题：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
1
2
3
4
5
6
7

示例 2：

输入：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

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10
1
2
3
4

解决：

和46，全排列一样的解法，只需要注意加几行代码来剪枝就好

var res [][]int
func permuteUnique(nums []int) [][]int {
	res = [][]int{}
	dfs(0,nums)
	return res
}

func dfs(x int,nums []int){
	if x==len(nums)-1{
		tmp := make([]int,len(nums))
		copy(tmp, nums)
		res = append(res, tmp)
		return
	}
	dict := make(map[int]bool,len(nums))
	for i := x;i<len(nums);i++{
		if _,ok := dict[nums[i]];ok{
			continue
		}
		dict[nums[i]]=true
		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
23
24
25
26