[LeetCode] 47. Permutations II

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

This problem is similar to 46. Permutations

To avoid duplication, the input array needs to be sorted first.

So we avoid picking number with same value as the start number of permutation.

Instead of swapping numbers, we need to take out the selected number to keep the sorted order of original array.

Time Complexity = O(N * N!)

Space Complexity = O(N * N!)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # sort to group number with same value together
        nums.sort()
        result = []
        
        def backtrack(tmp):
            if not nums:
            	# no more candidate number left
                if tmp:
                    result.append(partial)
                return
            
            for i in range(0, len(nums)):
                # skip number with same value to avoid duplicatation
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                
                # take the selected number out of candidate array
                n = nums.pop(i)
                
                backtrack(tmp + [n])
                
                # restore candidate array
                nums.insert(i, n)
                
        backtrack([])
        return result

Use hash table to avoid duplicate permutation

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])
            else:
                seen = set()
                for i in range(start, len(nums)):
                    if nums[i] in seen:
                        continue
                    
                    seen.add(nums[i])
                    
                    nums[start], nums[i] = nums[i], nums[start]
                    backtrack(start + 1)
                    nums[start], nums[i] = nums[i], nums[start]
        
        backtrack(0)
        return result

A hash table backed backtracking approach.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        counter = Counter(nums)
        keys = counter.keys()
        
        def backtrack(tmp):
            if len(tmp) == len(nums):
                result.append(tmp)
            else:
                for k in keys:
                    if counter[k] == 0:
                        continue
                        
                    counter[k] -= 1
                    backtrack(tmp + [k])
                    counter[k] += 1
        
        backtrack([])
        return result