47. Permutations II

输出一个有重复数字的数组的全排列。

思路： dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 6 star, 排序，然后dfs，需要去重
        nums.sort()
        rs = []
        self.dfs(nums, [], rs)
        return rs

    def dfs(self, nums, path, rs):
        if nums == []:
            rs.append(path)
            return
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], rs)