Chen's Blog

47. Permutations II

 
  • 2023年 06月13日

Promble

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

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

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Approach 1

use itertools libs.

Thought

  1. def res:Dict to store the final result, keys.
  2. loop item in permutations(nums)
    1. use dict key to de-repeat the final result
    2. res.get(key) vs res[key]: get will return None if key not exist
    3. res[item] = 0
  3. return list(res.keys())

Code

from itertools import permutations

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = {}
        for item in permutations(nums):
            # use dict key to de-repeat
            if res.get(item)==None:
                res[item] = 0

        return list(res.keys())
        
        # return set(list(permutations(nums)))

Approach 2

back track + dfs

Thought

  1. sort the nums.
  2. def res:list to store the result.
  3. def uest:list [False], the index is the nums[i] is used.
  4. def path:lsit the combintaion list to add in res.
  5. def dfs(nums, used, path, res)
    1. if len(path) == len(nums): res.append(path[:]) return # leaf note
    2. loop i in range(len(nums))
      1. pruning
      2. used[i] = True
      3. self.dfs()
      4. back track, used[i] = False
  6. return res

Code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)
        path = []

        nums = sorted(nums)

        self.dfs(nums, used, path, res)
        return res 

    def dfs(self, nums, used, path, res):
        # leaf nodes 
        if len(path) == len(nums):
            res.append(path[:])
            return 

        # not leaf nodes 
        for i in range(len(nums)):
            if used[i] or (i>0 and nums[i] == nums[i-1] and not used[i-1]):
                continue;
            used[i] = True
            self.dfs(nums, used, path+[nums[i]], res)
            # back track 
            used[i] = False
搜索