题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

golang 代码

var ans [][]int
var path []int
func permutation(nums []int) [][]int {
    path = make([]int,len(nums))
    sort.Ints(nums)
    order(nums,0,0,0)
    return ans
}

//nums:输入数组 u:把数组里第u个元素插入  
//s:上一个元素插入位置（如果不同，0开始；相同则s之后）state:插入位置通过二进制保存
func order(nums []int, u int, s int, state int) {
    if u == len(nums){
        var temp = make([]int,len(path))
        _ = copy(temp,path)
        ans = append(ans,temp)
        return
    }
    if u == 0 || nums[u] != nums[u-1] {
        s = 0
    }
    for i := s ; i < len(nums) ; i++ {
        if (state >> uint(i)) & 1 == 0 {
            path[i] = nums[u]
            order(nums, u + 1, i + 1 , state + (1 << uint(i)))
        }
    }
}