LeetCode-Python/python_solution/041_050/Permutations.py at master · CescWang1991/LeetCode-Python · GitHub

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
46
47
48
49
50
51
52
53
54
55
56
# 046. Permutations
# 047. Permutations II

class Solution(object):
    def permute(self, nums):
        multi = []
        for num in nums:
            rest = nums.copy()
            rest.remove(num)
            if len(rest) == 0:
                multi.append([num])
            else:
                rest_list = Solution().permute(rest)
                for list in rest_list:
                    multi.append([num] + list)

        return multi

    def permuteUnique(self, nums):
        multi = []
        for i in range(len(nums)):
            rest = nums.copy()
            del rest[i]

            # added code for 47. Permutation II: continue if the number is in the previous array
            if i != 0 and nums[i] in nums[:i]:
                continue
            # ---------------------------------

            if len(rest) == 0:
                multi.append([nums[i]])
            else:
                rest_list = Solution().permute(rest)
                for list in rest_list:
                    multi.append([nums[i]] + list)

        return multi

class Solution2:
    def permuteUnique(self, nums):
        """
        :type s: str
        :type ans: str
        """
        self.res = []
        self.dfs(nums, [])
        return self.res

    def dfs(self, nums, ans):
        if not nums:
            self.res.append(ans)
            return
        for i in range(len(nums)):
            if nums[i] not in nums[:i]:
                self.dfs(nums[:i]+nums[i+1:], ans + [nums[i]])
        return