高产的一周（bushi

题目：LeetCode剑指offer II 084.含有重复元素集合的全排列

头图来源:Ophelia-あるみっく-pixiv

是一道典型的dfs+剪枝的题，唯一需要注意的就是全排列的元素有重复，所以还需要为每个位置出现过的元素值进行标记来去重。

踩坑

大体思路有了，代码也写好了，自信满满提交后却发现了一个令我哭笑不得的错误。

按理说结果不应该会有重复的情况，怎么会是呢？！下面是我写的代码（错误版本）

func dfs(nums []int,idx int,used []int,tmp []int)[][]int{
    res:=[][]int{}
    if idx==len(nums){
        return append(res,tmp)
    }
    marki:=make(map[int]int)
    for i,num:=range nums{
        if used[i]==0{
            if _,ok:=marki[num];!ok{
                marki[num]=1
                used[i]=1
                tmp=append(tmp,num)
                res=append(res,dfs(nums,idx+1,used,tmp)...)
                tmp=tmp[:len(tmp)-1]
                used[i]=0
            }else{
                continue
            }
        }else{
            continue
        }
    }
    return res
}

tmp是个临时切片用来存储一次排列结果，当idx达到nums数量后将tmp加入到res（二维切片）中。
Go中的切片是引用类型，也就是说在将tmp加入到res中后下次tmp发生改变将会影响res中的内容。在append操作后如果超过的切片的len则会重新为切片分配更大的内存，此时用[:len(slice)-1]操作去掉切片的最后一个元素再进行append操作则不会重新分配内存（两次操作后的切片都指向了同一底层数组），因此两次操作的是同一块地址！（至少从力扣评测机的输出结果来看是如此）
为了解决这个问题就要用新的地址来存tmp中的数据，贴上修改后的代码

func dfs(nums []int,idx int,used []int,tmp []int)[][]int{
    //fmt.Println("idx=",idx,",used=",used,"tmp=",tmp)
    res:=[][]int{}
    if idx==len(nums){
        return append(res,append([]int{},tmp...)) //tmp是引用传递，需要重新初始化一个切片以防止后续tmp改变导致res改变
    }
    marki:=make(map[int]int)
    for i,num:=range nums{
        if used[i]==0{
            if _,ok:=marki[num];!ok{
                marki[num]=1
                used[i]=1
                tmp=append(tmp,num)
                res=append(res,dfs(nums,idx+1,used,tmp)...)
                tmp=tmp[:len(tmp)-1]
                used[i]=0
            }else{
                continue
            }
        }else{
            continue
        }
    }
    return res
}

总结

注意区分Go中的值类型和引用类型

• 值类型：int类、float类、string、struct和bool
• 引用类型：slice、map、func、chan、interface和指针

参考资料：

• golang的值类型，指针类型和引用类型&值传递&指针传递