[LeetCode] Challenge log 47

Posted on |
47. Permutations II

DFS problem. Same as 46, just to make sure at one level do not repeat duplicates.

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
Soulution:
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
# dfs solution
class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        def dfs(nums, st):
            if len(nums) == len(st): 
                res.append(st)
                return
            used = set()
            for i in range(len(nums)):
                if nums[i] is not None and nums[i] not in used:
                    used.add(nums[i])
                    temp = nums[i]
                    nums[i] = None
                    dfs(nums, st + [temp])
                    nums[i] = temp
                    
        if nums == []: return []
        res = []
        dfs(nums, [])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# use recursion to build all the possible set simultaneously.
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0: 
            return []
        elif n == 1:
            return [nums]
        else:
            res = []
            used = set()
            for i in range(n):
                if nums[i] not in used:
                    used.add(nums[i])
                    res += [[nums[i]] + x for x in self.permuteUnique(nums[:i] + nums[i+1:])]
        return res
0%