Co代码 $O(2^n)$

func permutation(nums []int) [][]int {

    n := len(nums)
    var p [][]int
    if n==0{
        return p
    }
    /*
    a标志nums中的数是否被选择过，re记录全排列的每一个结果，
    x记录nums的每一个元素前面是否有相同的元素（若没有就记录-1，若有就记录跟当前元素相同的元素的下标）
    */
    a := make([]int, n)         

    re := make([]int, n)        
    x := make([]int, n)

    //初始化x数组
    x[0] = -1
    for i := 1; i < n; i++ {
        j := i - 1
        for ; j >= 0; j-- {
            if nums[i] == nums[j] {
                x[i] = j
                break
            }
        }
        if j < 0 {
            x[i] = -1
        }
    }

    dfs(&x, &a, &re, &p, &nums, 0, n)
    return p

}

func dfs(x *[]int, a *[]int, re *[]int, p *[][]int, nums *[]int, i int, n int) {
//  if i == n {
//      *p = append(*p, *re)   这样提交的答案是错误的，才疏学浅，没看懂为啥，如果有大佬知道求指点
//  }
    if i == n {
        w := make([]int, n)     
        for j := 0; j < n; j++ {
            w[j] = (*re)[j]
        }
        *p = append(*p, w)
    }
    for j := 0; j < n; j++ {
        if (*a)[j] == 0 {
            if (*x)[j] != -1 && (*a)[(*x)[j]] == 0 {       // 若前面的元素与当前元素相同切未被选择则当前元素不予选择
                continue
            }
            (*a)[j] = 1
            (*re)[i] = (*nums)[j]
            dfs(x, a, re, p, nums, i+1, n)          //递归求解
            (*a)[j] = 0                             //回溯
        }
    }
}