47. Permutations II

Difficulty: Medium

link: https://leetcode.com/problems/permutations-ii/

1. Backtracking

$O(n!)$ runtime,

$O(n)$ space

用Counter記錄每個數字出現了幾次，在排列時同個數字就會當成同一類。

python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        counter = Counter(nums)
        
        result = []
        def backtracking(path):
            if len(path) == n:
                result.append(path)
                return
            
            for num in counter:
                if counter[num] > 0:
                    counter[num] -= 1
                    backtracking(path + [num])
                    counter[num] += 1
        
        backtracking([])
        return result

用swap的方式。

python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []

        def dfs(n_idx):
            if n_idx == n-1:
                res.append(nums[:])
                return

            seen_set = set()
            for i in range(n_idx, n):
                if nums[i] in seen_set:
                    continue
                nums[n_idx], nums[i] = nums[i], nums[n_idx]
                dfs(n_idx+1)
                nums[n_idx], nums[i] = nums[i], nums[n_idx]
                seen_set.add(nums[i])
        
        dfs(0)
        return res

tags: leetcode