47. Permutations II 全排列 II

题目

给定一个数组 nums，可能包含重复元素，返回所有可能的排列组合，不要重复。

解析

根据前一个递归，我们可以得到所有的全排列，现在的问题是，避免重复，要避免重复，就要知道重复是如何发生的。
对于 [1,1,2] 这个数组，当我们按 0,1,2 顺序排列时，得到 1,1,2 当按照 1,0,2 顺序排列时，得到 1,1,2 。由此可知，重复发生的条件是，当 pick 一个数字时，如果当前数子已经 pick 过了，并且当前位置在 pick 过位置之前，则必定发生重复。
换句话说，pick 相同的数字，只能按照一个顺序进行，不能先 pick 了 idx = 1 的数字，再 pick idx = 0 的数字。

如何解决这个问题，

1. 首先将数组排序，这样我们就能把相同的数字集中在一起了。
2. 然后我们开始进行 pick。每次 pick 的时候，我们将游标置于连续相同数字的头部
3. 然后按照上一个递归。
4. 移动游标的时候，我们应将游标直接移动到下一个不同的数字上，这样保证不会先选后边的，再选前边的。

伪代码

sort(nums)
for i<len(nums)
  res := nums[i]
  nums[i] = FLAG
  rst = append(rst, res+func(nums))
  nums[i] = res
  if nums[i+1] == nums[i]
    i++
  return rst

代码

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    return permute(nums)
}

func permute(nums []int) [][]int {
    var rsts [][]int
    for i:=0;i<len(nums);i++ {
        if nums[i] == 1<<31-1 {
            continue
        }
        res := nums[i]
        nums[i] = 1<<31-1
        rst := permute(nums)
        nums[i] = res
        if rst == nil {
            rsts = [][]int{{res}}
        }
        for i:= range rst {
            rsts = append(rsts, append(rst[i], res))
        }
        for i<len(nums)-1 && nums[i+1] == nums[i] {
            i++
        }
    }
    return rsts
}

image.png