menu

[LeetCode] 047. Permutations II

Problem (Medium)

047. Permutations II

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

Example:

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

Approach 1: (My Solution) Backtracking

Idea

  • Same idea as the last problem, add another paramter in the backtracking recursion: index_pool to differentiate the duplicates.
  • In the last step, remove duplicate items by set().

Solution

class Solution1:
    def permuteUnique(self, nums):
        """ 
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.backtrack(nums,[], [], res)
        res = set([tuple(i) for i in res])
        return res 

    def backtrack(self,nums, index_pool, item, res):
        if len(item) == len(nums):
            res.append(item)
            return
        for i in range(len(nums)):
            if i in index_pool:
                continue
            self.backtrack(nums, index_pool + [i], item + [nums[i]], res)

Complexity

  • Time: $O()$
  • Space: $O()$

Approach 2: Tricky Solution ***

Idea

9-line python solution with 1 line to handle duplication, beat 99% of others :-)

Very similar to Permutation I, see explanations in https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution. To handle duplication, just avoid inserting a number before any of its duplicates.

Solution

def permuteUnique(self, nums):
    ans = [[]]
    for n in nums:
        new_ans = []
        for l in ans:
            for i in xrange(len(l)+1):
                new_ans.append(l[:i]+[n]+l[i:])
                if i<len(l) and l[i]==n: break              #handles duplication
        ans = new_ans
    return ans

Complexity

  • Time: $O()$?
  • Space: $O()$?



KF

Comments