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

Another classical backtracking problem. Let us try to built our sequence element by element, inserting new element in different places. Imagine, that we have [1,3,1,2]. Then our building process will look like:

  1. [1] on the first step we have not choice, so here we have only one option.
  2. Now, we need to insert next element somewhere, and we have two options: before and after, so we have [1,3] and [3,1] options here.
  3. Now we need to insert new element 1. The problem here is that when we insert it, we can have repeating answers, so the rule is: insert in only before the already existing occurrences of this element. So, in [1,3] we can only insert it before 1 and get [1,1,3] and in [3,1] we have two places to insert and we have [1,3,1] and [3,1,1].
  4. Finally, we want to insert 2 to the each of existing answers, and we have: [2,1,1,3], [1,2,1,3], [1,1,2,3], [1,1,3,2], [2,1,3,1], [1,2,3,1], [1,3,2,1], [1,3,1,2], [2,3,1,1], [3,2,1,1], [3,1,2,1], [3,1,1,2]

Complexity: Time complexity is O(Q n), where Q is number of desired permutations and n is length of nums, because every time we build our sequence we write it in our final answer, that is there will be no dead-ends. Q can be evaluated, using multinomial coefficients https://en.wikipedia.org/wiki/Multinomial_theorem. Space complexity is the same.

class Solution:
    def permuteUnique(self, nums):
        def dfs(ind, built):
            if ind == len(nums):
                ans.append(built)
                return

            stop = built.index(nums[ind]) if nums[ind] in built else ind
            
            for i in range(stop+1):
                dfs(ind+1, built[:i]+[nums[ind]]+built[i:])

        ans = []
        dfs(0, [])  
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0047