<p>Given a collection of numbers, <code>nums</code>,&nbsp;that might contain duplicates, return <em>all possible unique permutations <strong>in any order</strong>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,2]
<strong>Output:</strong>
[[1,1,2],
 [1,2,1],
 [2,1,1]]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 8</code></li>
	<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>
</ul>

from sortedcontainers import SortedDict

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        # Loop
        ## Current position should be updated.
        ## If empty (i.e. -1), get the lowest number from 'avail', and use that to fill the current position and move right. After moving right, if position is outside array, record new permutation, and move back left.
        ## If already filled, increment it.
        ### Check in 'avail' for lowest number greater than number
        ### If such a number is present, replace current number with that number and move right. After moving right, if position is outside array, record new permutation, and move back left.; else mark this position as empty and move left. After moving left, if position is outside array, break out of loop (all permutations have been generated)
        
        # At every step in the loop, if something is removed from the main array, add it to 'avail'. If something from 'avail' is used in the main array, remove it from 'avail'

        result = []


        def moveRight():
            nonlocal perm, pos, n

            perm[pos] = a

            pos += 1
            if pos >= n:
                pos = n - 1
                result.append(perm.copy())

        
        def decrAvail(key):
            nonlocal avail

            if key in avail:
                avail[key] -= 1

                if avail[key] <= 0:
                    avail.pop(key)


        def incrAvail(key):
            nonlocal avail

            if key in avail:
                avail[key] += 1
            else:
                avail[key] = 1


        def decrAvailInd(index):
            nonlocal avail

            if index >= 0 and index < len(avail):
                key, val = avail.peekitem(index)

                decrAvail(key)

                return key, val
            
            return None


        n = len(nums)
        pos = 0
        perm = [None] * n
        avail = SortedDict()

        for e in nums:
            incrAvail(e)

        while True:
            if perm[pos] is None:
                a, b = decrAvailInd(0)
                perm[pos] = a
                moveRight()

            else:
                p = avail.bisect_right(perm[pos])

                if p >= 0 and p < len(avail):
                    a, b = decrAvailInd(p)

                    incrAvail(perm[pos])

                    perm[pos] = a

                    moveRight()
                else:
                    incrAvail(perm[pos])
                    perm[pos] = None
                    pos -= 1

                    if pos < 0:
                        break


        return result

17300