algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

permutations-ii.py (901B)

      1 class Solution:
      2     
      3     def permute(self,remaining, current):
      4         
      5         if len(remaining) == 0:
      6             self.result.append(current.copy())
      7             return
      8         
      9         k  = list(remaining.keys())
     10 
     11         for rem in k:
     12             count = remaining[rem]
     13             count -= 1
     14             if count == 0:
     15                 del remaining[rem]
     16             else:
     17                 remaining[rem] = count
     18             current.append(rem)
     19             self.permute(remaining, current)
     20             remaining[rem] = count + 1
     21             current.pop()
     22 
     23         return
     24     
     25     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
     26         self.result = []
     27         numDict = {}
     28         for num in nums:
     29             if numDict.get(num) is None:
     30                 numDict[num] = 1
     31             else:
     32                 numDict[num] += 1
     33         self.permute(numDict, [])
     34         return self.result