LC47 Permutaions II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # time O(N!)  space O(N)
        d = collections.Counter(nums)
        self.res = []
        self._btrack(nums,d,[])
        return self.res
    def _btrack(self,nums,counter,path ):
        if len(nums) == len(path):
            self.res.append(path[:])
        for num in counter: # loop will not pick dupplication 
            if counter[num] > 0:
                path.append(num)
                counter[num] -= 1
                self._btrack(nums,counter,path)
                path.pop()
                counter[num] += 1
        
        

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # time O(N!)  space O(N)
        # main idea: to avid inserting a number after it has appeared before
        res = [[]]
        if not nums:
            return res
        for num in nums:
            res_new = []
            for group in res:
                for i in range(len(group)+1): # +1 to prevent off boundry e.g. group =  []
                    res_new.append(group[:i]+[num]+group[i:])
                    if i < len(group) and group[i] == num:
                        break # handle duplication
            res = res_new
        return res