Leetcode 47.全排列II

Posted on |

47.全排列II

题目

类似于46.全排列

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

1
2
3
4
5
6
7
8
9
示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

方法1：回溯法

由于输入可能包含重复数字，所以就要保证去重。先排序然后创建Array记录访问过的数字，然后前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        nums.sort()         # 计得要排序，这样子重复的元素才会被放置在一起
        used=[False for _ in range(len(nums))]
        self.backtrack(nums, res, [],used)
        return res

    def backtrack(self, nums, res, temp, used):
        if len(temp)==len(nums):
            res.append(list(temp))
        else:
            for i in range(len(nums)):
                if used[i] or i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                temp.append(nums[i])
                used[i]=True

                self.backtrack(nums, res, temp, used)
                temp.pop()
                used[i]=False

# nums, res, temp, used
# [1, 1, 2] [] [] [False, False, False]
# [1, 1, 2] [] [1] [True, False, False]
# [1, 1, 2] [] [1, 1] [True, True, False]
# [1, 1, 2] [] [1, 1, 2] [True, True, True]
# pop:  2
# pop:  1
# [1, 1, 2] [[1, 1, 2]] [1, 2] [True, False, True]
# [1, 1, 2] [[1, 1, 2]] [1, 2, 1] [True, True, True]
# pop:  1
# pop:  2
# pop:  1
# [1, 1, 2] [[1, 1, 2], [1, 2, 1]] [2] [False, False, True]
# [1, 1, 2] [[1, 1, 2], [1, 2, 1]] [2, 1] [True, False, True]
# [1, 1, 2] [[1, 1, 2], [1, 2, 1]] [2, 1, 1] [True, True, True]
# pop:  1
# pop:  1
# pop:  2
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        self.helper(nums, 0, len(nums))
        return self.res

    def helper(self, nums, position, end):
        if position==end:
            self.res.append(nums[:])
        else:
            used=set()
            for i in range(position, end):
                if nums[i] not in used:
                    used.add(nums[i])
                    nums[i],nums[position]=nums[position],nums[i]
                    self.helper(nums, position+1, end)
                    nums[i],nums[position]=nums[position],nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        if nums:
            nums.sort()
            self.dfs(nums, res, [])
        return res

    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
        else:
            for i,n in enumerate(nums):
                if i and nums[i]==nums[i-1]:
                    continue
                self.dfs(nums[:i]+nums[i+1:], res, path+[n])