LeetCode-47. 全排列 II - sheep44044的小站

回溯#

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
输入：nums = [1,1,2]
2
输出：
3
[[1,1,2],
4
 [1,2,1],
5
 [2,1,1]]

示例 2：

1
输入：nums = [1,2,3]
2
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路:相较于 46. 全排列 这里多了一步就是如何判断重复，通过if i > 0 && nums[i] == nums[i-1] && !used[i-1]这个语句，能避免重复的情况直接跳过

唯一需要注意的是i > 0 && nums[i] == nums[i-1]顺序不要写反了，不然会执行错误

1
func permuteUnique(nums []int) [][]int {
2
    sort.Ints(nums)
3

4
    res := [][]int{}
5
    path := []int{}
6
    used := make([]bool, len(nums))
7

8
    var backtrack func()
9
    backtrack = func() {
10
        if len(path) == len(nums) {
11
            res = append(res, append([]int(nil), path...))
12
        }
13

14
        for i := 0; i < len(nums); i++ {
15
            if used[i] {
16
                continue
17
            }
18

19
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
20
                continue
21
            }
22

23
            path = append(path, nums[i])
24
            used[i] = true
25
            backtrack()
26
            path = path[:len(path)-1]
27
            used[i] = false
28
        }
29
    }
30

31
    backtrack()
32
    return res
33
}