Leetcode 46

Posted on | | 阅读数
Words count in article: 261 | Reading time ≈ 1

Question1

Solution

采用递归的方法。创建一个[False, False, …, False]的序列，如果一个数出现过了，就将其改为True。同时在递归返回结果后将数列恢复原样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        
        results, flags = [], [False] * len(nums)
        self.getP(nums, results, flags, [])
        return results
    
    def getP(self, nums, results, flags, temp):
        if len(temp) == len(nums):
            results.append(temp[:])
            return
        
        for i in range(len(nums)):
            if flags[i]:
                continue
            
            temp.append(nums[i])
            flags[i] = True
            self.getP(nums, results, flags, temp)
            temp.pop()
            flags[i] = False

Solution2

Dfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        results = []
        nums.sort()
        self.dfs(nums, [], results)
        return results
    
    def dfs(self, nums, temp, results):
        if not nums:
            results.append(temp)
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], temp+[nums[i]], results)

Question2

Solution

注意考虑nums里面的重复数字带来的重复结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        results = []
        nums.sort()
        self.dfs(nums, [], results)
        return results
    
    def dfs(self, nums, temp, results):
        if not nums:
            results.append(temp)
        
        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], temp+[nums[i]], results)