LeetCode 47. Permutations II

Description

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

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

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

Explanation

Backtracking to find permutations. The difference between this Permutations II and Permutation is that this problem has duplicate values. So we should skip the element by position not by value when building permutations. Also if the permutation has been found, we don’t need to add them to the final result list.

Python Solution

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        results = []
        
        nums = sorted(nums)
        
        visited = set()
        self.helper(results, nums, [], 0, visited)
        
        
        return results
    
    def helper(self, results, nums, permutation, start, visited):
        if len(permutation) == len(nums) and permutation not in results:
            results.append(list(permutation))
            return
        
        for i in range(len(nums)):
            if i in visited:
                continue
            
            visited.add(i)
            permutation.append(nums[i])
            
            self.helper(results, nums, permutation, start, visited)
            
            permutation.pop()
            visited.remove(i)
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *