Golang:
写在前面：这题如果是用我46的代码是改不出来的，除非得到所有结果再去删除重复的，但这样自然就没什么意思了，我在这道题上花了差不多整整半天，去研究了深度优先、回溯和剪枝，并试图应用进我的代码里，但最终还是失败了。
思路：可以参见liweiwei大佬的题解，很有帮助。我只在这里描述下我上一题的代码为什么无法应用在这一次的题里。我上一题的解法是，如果有[1,2,3,4,5]这样的数组，我在第一轮的起始数组分别是[1,2,3,4,5]，[2,1,3,4,5]，[3,2,1,4,5]，[4,2,3,1,5]等。即我每次会将第i位和第1位互换，这在全排列里是行得通的。而深度优先加回溯第一轮的起始数组是[1,2,3,4,5]，[2,1,3,4,5]，[3,1,2,4,5]，[4,1,2,3,5]等。注意，在第一轮的数组里，我们去掉第一位数，会变成[2,3,4,5]，[1,3,4,5]，[2,1,4,5]，[2,3,1,5]，注意看，它们是不按照顺序排列的，而深度优先的方法处理完的数组则是按顺序排列的。所以，深度优先会保证在变动第i位后，剩下的数组按照顺序排列。而这一题的排列，顺序是很重要的，可以保证我们剪枝的准确性。在初始，我们对nums数组进行排序后，使用深度优先的方法会保证剩下每一次变动都是按照顺序逐步来的，而我原始全排列的方法在第一轮处理后，数组就不按照顺序来了，自然会报错。
代码如下：
func permuteUnique(nums []int) [][]int {
var res [][]int
if len(nums)==0 {
return [][]int{{}}
}
sort.Ints(nums)
used:=make([]int,len(nums))
var path []int
dfs(nums,0,&path,used,&res)
return res
}
func dfs(arr []int,depth int,path *[]int,used []int,res *[][]int) {
if depth==len(arr){
//保存数组并终止递归
temp:=make([]int,len(arr))
copy(temp,*path)
*res= append(*res, temp)
return
}
for i:=0; i<len(arr); i++ {
if used[i]==0 {
if i>0&&arr[i]==arr[i-1]&&used[i-1]==0 {
continue
}
*path=append(*path, arr[i])
used[i]=1
dfs(arr,depth+1,path,used,res)
//回溯，起始就是used数组标记回溯+path数组减一（切片实现很麻烦）
used[i]=0
temp2:=*path
temp2=temp2[:len(temp2)-1]
*path= temp2
}
}
}
有疑问加站长微信联系（非本文作者）
